Re: Provability
- From: Keith Ramsay <kramsay@xxxxxxx>
- Date: Tue, 30 Oct 2007 00:42:48 -0700
On Oct 23, 7:57 am, Victor Porton <por...@xxxxxxxx> wrote:
|For famous hypothesis such as Millennium Prize problems (or to be yet
|more specific forP=NPproblem)...
|
|... how we can (or cannot) be sure that the hypotheses or its
negation
|is provable.
In none of the cases can we be sure yet, except of course
for the Poincare conjecture which has been proven.
A lot of famous conjectures have the property that if the
conjecture is false, a counterexample can in principle be
verified (using some standard axiom system). The Riemann
hypothesis is this way, for example. If zeta has a zero in
the wrong place, there's a calculation that would show that
it does. I can't swear to it, but I believe the Poincare
conjecture was like this before it was proven: a
counterexample could in principle be checked with a finite
calculation.
The Birch and Swinnerton-Dyer conjecture may not be
completely that way yet, but it's at least close. If there
is a counterexample, it's an elliptic curve (given by a
cubic equation y^2=x^3+ax+b where a and b are integers). One
has to confirm the order of the zero of a computable function
associated with the curve, which as with the zeta function
is possible in principle, and then show that the curve has
the "wrong number" of solutions of certain kinds. That last
part can probably be done in every case, but I'm doubtful
whether it's proven.
I don't know enough about the Hodge conjecture to know, but
I think it may also at least be close to the situation where
a counterexample would necessarily be demonstrable in a
familiar formal axiom system.
The problems having to do with Navier-Stokes and Yang-Mills
both have to do with the existence of solutions to PDEs.
Perhaps someone knows the status of such questions.
|There are statements which are unprovable nor true nor false in ZFC.
|
|For a specific example can we be sure that eitherP=NPorP!=NPis
|provable?
The P=NP problem has an amusing equivalent. First, as you
may know there are NP problems which have a kind of
"universal" property relative to the others, so that if one
of them is in P, then all of NP is in P too (the NP-complete
problems). Boolean satisfiability is a convenient example:
given a formula with variables combined by connectives "and",
"or", and "not", is it possible to substitute "true" or
"false" for the variables is such a way as to make the
formula evaluate to "true"?
P=NP is equivalent to the existence of an algorithm that
finds a solution within some polynomial time bound, if it
exists. Amusingly, we can write down an algorithm which does
this if any algorithm does. It's called a Levin universal
search. It enumerates possible searching algorithms A1,A2,...
and simulates them, giving them the problem as input,
spending approximately 1/2^n of its time simulating an
algorithm A_k if it takes n bits to represent A_k in a given
self-terminating language. By self-terminating, I mean that
the universal Turing machine that runs the program is able
to tell where the program ends just from the program itself.
If some algorithm A_t is a polynomial-time algorithm for
finding solutions to boolean satisfiability problems (when
they exist), then Levin's search is such an algorithm too.
It just takes 2^N times as long, where N is the number of
bits in A_t. This is impractical, but in principal the Levin
search will find a solution in polynomial time too, just
with a huge constant factor.
So P=NP can be rephrased as a question about how long the
Levin search might take to find solutions.
Each polynomial is bounded above by n^C + C for some integer
C. First take C0 to be bigger than the degree. Then increase
it enough to deal with the (finitely many) cases where
n^{C0}+C0 is less than the polynomial. For each case of the
problem where a solution exists, whose length is n, we can
ask, what is the smallest value of C such that the Levin
search finds a solution within n^C+C steps? If there is some
fixed C that is large enough for all cases, then P=NP. If
the needed value of C is unbounded, then P<>NP. Thus P=NP is
equivalent to some computable sequence of integers being
bounded.
There's no fixed formal system in which if a computable
sequence of integers is bounded, then the boundedness can
be proven in the system. If there is no upper bound, then in
a vague sense it's even further from true that the
unboundedness would necessarily be provable in a given system.
One has to prove that for each candidate bound, there exists
a problem with a solution that Levin search takes longer than
that bound to find.
Keith Ramsay
.
- References:
- Provability
- From: Victor Porton
- Provability
- Prev by Date: Re: Probability with dice..
- Next by Date: Re: JSH: Why self-encryption?
- Previous by thread: Re: Provability
- Next by thread: Complete Solutions Manual for Introduction to the Practice of Statistics 5th edition
- Index(es):
Relevant Pages
|
