Consequences of NP-Complete in QP?
I believe(*) I have an algorithm for solving NP-Complete problems that has quasi-polynomial (or at least, sub-exponential, not sure yet https://math.codidact.com/posts/295827) complexity. This by itself would only mean that NP-Complete is in QP. So far, that'd be a nice improvement, although it'd be far from ideal.
However, there's Ladner's theorem https://en.wikipedia.org/wiki/NP-intermediate. Wikipedia says of it, that it asserts that:
if P ≠ NP, then NPI is not empty; that is, NP contains problems that are neither in P nor NP-complete. Since it is also true that if NPI problems exist, then P ≠ NP, it follows that P = NP if and only if NPI is empty.
With NPI being NP-Intermediate, problems which require quasi-polynomial complexity to solve.
The interesting part from the quote is that if NP-Intermediate is empty, then P==NP.
The question is:
- If NP-Complete is in QP, does it imply that NP-Intermediate is empty? Or is it compatible that NP-Intermediate be non-empty with NP-Complete being in QP?
The answer to this question would be quite important. If NP-Complete being in QP would imply that NP-Intermediate would be empty, then, P==NP, which means that a quasi-polynomial algorithm for solving NP-Complete would itself be proof that a better yet unknown algorithm in P exists.
On the other hand, if NP-Complete being in QP doesn't imply NP-Intermediate being empty, the question of P=?NP would remain unanswered.
Also, is Ladner's theorem known to be 100% certain?
(*): I believe it works. I'm doing a lot of checks to verify it's correct, but so far, it seems correct. I may have made a mistake analyzing the complexity of the algorithm, but experiments so far confirm the run-time. I may have also made a mistake in finding the absolute best solution; this is harder to prove, as there's no oracle that can confirm whether or not a better solution exists (other than carefully checking that the algorithm is exhaustive, but this is subject to possible mistakes in my own careful checks), so I'm running benchmarks, and different algorithms (but that's limited). If this continues seeming correct, I'll publish something soon.
2 answers
You are accessing this answer with a direct link, so it's being shown above all other answers regardless of its score. You can return to the normal view.
With NPI being NP-Intermediate, problems which require quasi-polynomial complexity to solve.
No, NPI is problems in NP which are not in P and are not in NPC. The only claims about complexity which follow easily from the definition are that they take superpolynomial but no worse than exponential time (and, indeed, can be solved in exponential time with polynomial space).
0 comment threads
(Disclaimer: I'm neither well-versed in computational complexity nor am I familiar with the relevant literature, so I may very well have missed something.)
By Ladner's theorem, if NP is unequal to P then there are intermediates between NP and P. Thus, if the best NP-complete problem is in QP, then there are problems in NPI.
Your suggestion that, if we can find an NP-complete algorithm in QP, then might be able to prove that P = NP is interesting but I am reasonably sure that it cannot be done with usual techniques. For instance I believe there are oracles $Ω$ relative to which NP is in QP but not in P---thus any technique that would prove that $NP \subseteq QP$ implies NP = P would have to be sophisticated enough that it wouldn't extend to a proof that $NP^Ω \subseteq QP^Ω$ implies $NP^Ω = P^Ω$.
0 comment threads
1 comment thread