Thursday, October 06, 2016

[oobhikls] Unsatisfying P != NP

Someday, it may be proven that P < NP; however, the proof might be disappointing or unsatisfying.  It might be proven that one (obscure) NP problem is not in P, but it unfortunately provides no insight as to whether another NP problem, a problem that you care about, perhaps integer factorization, is not in P.  It could be, or it could not be (assume the proof technique does not generalize).  Or it might be proven that in the worst-case, a problem cannot be solved in polynomial time, but this isn't helpful if your particular instance of the problem isn't in that worst-case class.  For example, it might be proven that factoring requires super-polynomial time for a set (infinite sequence) of very rare, very difficult to construct integers, but this doesn't help for cryptography because practically all RSA numbers will not be in that class.

If it is proven that P = NP by showing a polynomial time algorithm for an NP-complete problem, then things will be very exciting (or practically, perhaps not, if the exponent is huge): by reduction it will provide a polynomial-time algorithm for every problem in NP.  Is it possible that P = NP might be proven not going through the NP-complete route and yield a similarly disappointing or unsatisfying proof?  Perhaps a non-constructive proof: there exists some deterministic Turing machine equivalent to a nondeterministic Turing machine...

No comments :