Re: Computability in principle

From: Fergus Henderson (fjh_at_cs.mu.oz.au)
Date: 11/11/03 

Date: Tue, 11 Nov 2003 04:13:30 GMT

Joe Marshall <jrm@ccs.neu.edu> writes:

>Fergus Henderson <fjh@cs.mu.oz.au> writes:
>
>> I think you are misremembering. The M-algorithm takes as input an
>> algorithm, not a constructive proof.
>
>Here's what the paper says:
> ``Given a formal specification of a problem depending on some
> parameter x (element of X), we are interested in a fast algorithm
> computing solution y (element of Y). This means that we are
> interested in a fast algorithm computing f: X->Y, where f is a
> formal (logical, mathematical, not necessarily algorithmic),
> specification of the problem.''
>
>So f is some formal specification, not necessarily an algorithm, but
>necessarily something you could manipulate with a computer.

I stand corrected. It takes as input either "a given algorithm ...
or, more generally a specification of a function".

However, a specification is not the same thing as a proof!

>> No, this is wrong/meaningless. As we discussed already,
>> there is no easy way to use the M-algorithm to determine if P=NP.
>
>I *know* that M-algorithm cannot solve P=NP

Convince the rest of us, and earn your Turing award!

>(probably,

Ah, there's the rub.

>it could be that P *does* = NP and that this is provable, but assuming
>that it isn't).

You don't have any truly convincing grounds for that assumption.

>Given that it *can* solve well-defined problems for which it
>can find a proof, then `P=NP' must not be `well-defined' `formal
>specification' of the problem.

The M-algorithm can only solve _solvable_ well-defined problems.
The claim in the paper is not that it solves all well-defined problems,
but rather than it "solves all well-defined problems *as quickly as
the fastest algorithm computing a solution* ... save for a factor 5
and ... additive terms". If there is no algorithm computing a solution,
then this claim is empty.

Also, your statement here is confusing, because you blur the distinction
between (a) solving an NP-hard problem in P time and (b) "solving the
P=NP problem", i.e. either proving P=NP or proving P!=NP.
If (a) is provably unsolvable, then (b) is solvable, with answer "P!=NP".

Even if you _assume_ that P=NP is not provable, that does not show
that the P=NP problem is "not well defined". The other alternatives
are that P!=NP is provable, or that the "P=NP" problem is well-defined,
but unsolvable. 

-- 
Fergus Henderson <fjh@cs.mu.oz.au>  |  "I have always known that the pursuit
The University of Melbourne         |  of excellence is a lethal habit"
WWW: <http://www.cs.mu.oz.au/~fjh>  |     -- the last words of T. S. Garp.

Relevant Pages

  • Re: Computability in principle
    ... > algorithm, not a constructive proof. ... ``Given a formal specification of a problem depending on some ... computing solution y. ...
    (comp.lang.lisp)
  • Re: Python from Wise Guys Viewpoint
    ... > that solves the collatz problem? ... just supply the algorithm that solves it. ... Assuming you have a provable formal specification of the collatz ... journal = "International Journal of Foundations of Computer Science", ...
    (comp.lang.lisp)
  • Re: Python from Wise Guys Viewpoint
    ... > if a putative input/output pair is indeed correct. ... I can render any specification ... a formal system in which the correctness of the fastest algorithm can be ... a constructive proof that P=NP is decidable would be ...
    (comp.lang.lisp)
  • Re: ZFC
    ... there is a long running tradition that constructive proof = ... > constructive proof of an AE-statement yields an algorithm, ... wasting my CPU time. ...
    (comp.theory)
  • Re: symplectic group generators
    ... > is given an arbitrary symplectic matrix, an algorithm to express it in ... This topic should be included in any basic publication on Siegel modular ...
    (sci.math.research)