If P=NP then we HAVE an alg for SAT.

I am writing up the result of my survey of peoples opinion of P vs NP (it will be in a SIGACT News, in Lane's Complexity Column, in 2019.) Some  people wrote:

                          P=NP but the proof will be nonconstructive and have a large constant.

Large constant could happen.

If by nonconstructive they mean not practical, then yes, that could happen.

The following does not quite show it can't happen but it does give one pause:  an old result of Levin's shows that there is a program you could write NOW such that if P=NP then this program decides SAT except for a finite number of formulas (all of which are NOT in SAT) and can be proven to work in poly time (I will later give three pointers to proofs). The finite number of formulas is why the people above may still be right. But only a finite number- seems like a weak kind of nonconstructive.

Since I am teaching crypto I wondered about Factoring. An old result of Gasarch (I proved it this morning -- I am sure it is already known) shows that there is a program you could write NOW such that if Factoring is in P then this program factors a number ALWAYS (none of this finite exception crap) and can be proven to work in poly time. Even so, the algorithm is insane. If someone thought that factoring in P might be nonconstructive, my construction disproves it in such an absurd  way that  the notion that factoring could be in P nonconstructively should be taken seriously but not literally. There should be a way to say formally:

I believe that FACTORING is in P but  any poly-time algorithm is insane (not even looking at the constants) and hence could never be implemented.


Not sure how to define insane.

Three pointers:

Stack Exchange TCS:  here

Wikipedia: here

My slides (also include factoring result): here

Question: Can the SAT result be improved to be an algorithm that is ALWAYS right? Is there a way to show that it can't be (unless, say P=NP).

Question: What can be said about Graph Isomphism in this context? The proof for SAT is easily adpated to this case (all we used about SAT was that it was self-reducible). But can we get our GI algorithm to never make a mistake?


Computational Complexity published first on Computational Complexity