[FOM] Chaitin's Omega/P vs. NP
joeshipman at aol.com
joeshipman at aol.com
Fri Apr 8 14:42:37 EDT 2011
Not necessarily. With an oracle for the halting problem we would know
whether there was a proof in ZFC or P = NP, a proof in ZFC of P not=
NP, or neither, or both (in which case there would be bigger issues
than P-NP to worry about). But "neither" would mean the P-NP problem
was still unsettled.
We can ALMOST settle it though. There is a universal algorithm X to
solve SAT which has the property that, if P=NP, X runs in polynomial
time. We create a "clocked" version X' which runs X for (input
length+1)^(googleplex) steps and then halts if X failed to halt, and
another program X'' which sequentially runs X' on all instances of SAT,
and ask the oracle for the halting problem if X'' ever halts. If the
answer is "no", then P=NP, and if the answer is "yes", then any
polynomial-time algorithm for SAT is ridiculously infeasible. -- JS
-----Original Message-----
From: pax0 at seznam.cz
To: fom at cs.nyu.edu
Sent: Fri, Apr 8, 2011 11:03 am
Subject: [FOM] Chaitin's Omega/P vs. NP
Please does someone know if we knew the well-known Chaitin's Omega(the
probability of halting a chosen universal Turing machine on a random
input)to enough bits, then we could settle the P vs. NP problem?Thank
you, Jan Pax_______________________________________________FOM mailing
listFOM at cs.nyu.eduhttp://www.cs.nyu.edu/mailman/listinfo/fom
More information about the FOM
mailing list