Re: Provability

On Tue, 23 Oct 2007 23:01:05 GMT, Michael Press <rubrum@xxxxxxxxxxx>
wrote:

In article
<rbisrael.20071023142716$7fa6@xxxxxxxxxxxxxxxx>,
Robert Israel <israel@xxxxxxxxxxxxxxxxxxxxxxxxxxxxx>
wrote:

Victor Porton <porton@xxxxxxxx> writes:

For famous hypothesis such as Millennium Prize problems (or to be yet
more specific for P=NP problem)...

... how we can (or cannot) be sure that the hypotheses or its negation
is provable.

We can't. In some cases we can do half of this: e.g. if the Riemann
hypothesis or Goldbach's conjecture happens to be false, then its
negation is provable. But if it is true, there is no guarantee that
there is a proof of that.

There are statements which are unprovable nor true nor false in ZFC.

For a specific example can we be sure that either P=NP or P!=NP is
provable?

No. This is even worse than the Riemann hypothesis in that regard:
thus if P=NP there is a polynomial-time algorithm for solving an NP-complete
problem, but there might not be a proof that this algorithm works.

The notion of algorithm shares an important characteristic
with the notion of theorem. A computational method is not
an algorithm until we have accepted a proof of its efficacy.

Not according to the definition of "algorithm" I know.

Both of the following routines are algorithms. One of them
is an algorithm which gives the right answer to the
question "Is RH true?":

def SayYes:
return "yes"

def SayNo:
return "no"

I don't know which one gives the right answer, but
that doesn't change the fact that they are both
algorithms and one of them works.


************************

David C. Ullrich
.

Relevant Pages

  • Re: Provability
    ... Robert Israel ... how we can be sure that the hypotheses or its negation ... This is even worse than the Riemann hypothesis in that regard: ... but there might not be a proof that this algorithm works. ...
    (sci.math)
  • Re: What assignment and equivalence syntax do you prefer?
    ... > Yes, like an arrow. ... You even see it in algorithm descriptions ... > negation), but again, that's outside ASCII (and makes the code ...
    (comp.programming)
  • Re: P = NP, what are your opinions?
    ... There exists an algorithm X such that, given as input an algorithm Y ... The interesting thing about this is that it phrases the ... negation of P = NP as an existential problem. ...
    (comp.theory)
  • Re: P = NP, what are your opinions?
    ... There exists an algorithm X such that, given as input an algorithm Y ... The interesting thing about this is that it phrases the ... negation of P = NP as an existential problem. ...
    (comp.theory)
  • Re: Riemann Hypothesis and P vs NP
    ... ]> Right, but the correctness of the algorithm I mentioned, did. ... ]Riemann hypothesis is true, Miller-Rabin runs in polynomial time. ...
    (comp.theory)
Loading