[FOM] Chaitin's Omega/P vs. NP

[joeshipman at aol.com]

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