Is there a known, explicit example of an algorithm with the property such that if $P\neq NP$ then this algorithm doesn't run in polynomial time and if $P=NP$ then it does run in polynomial time?
$\begingroup$
$\endgroup$
3
-
9$\begingroup$ Sort of. If P = NP, Levin’s universal search algorithm runs in polynomial time on accepting instances en.wikipedia.org/wiki/… $\endgroup$– Emil JeřábekCommented Oct 19, 2018 at 16:29
-
$\begingroup$ @Emil: if P=NP then also P=coNP, so can't you simultaneously do Levin search on the complement of your language, thus giving a truly poly time algorithm on all instances? $\endgroup$– Joshua GrochowCommented Oct 21, 2018 at 2:12
-
3$\begingroup$ @JoshuaGrochow In order to express the language as coNP, I would need first to know the polytime algorithm for NP, defeating the whole purpose. $\endgroup$– Emil JeřábekCommented Oct 21, 2018 at 9:45
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
15
If you assume that $P=^?NP$ is provable in PA (or ZFC), a trivial example is the following:
Input: N (integer in binary format)
For I = 1 to N do
begin
if I is a valid encoding of a proof of P = NP in PA (or ZFC)
then halt and accept
End
Reject
Another - less trivial - example that relies on no assumption is the following:
Input: x (boolean formula)
Find the minimum i such that
1) |M_i| < log(log(|x|)) [ M_1,M_2,... is a standard fixed TM enumeration]
2) and M_i solves SAT correctly
on all formulas |y| < log(log(|x|))
halting in no more than |y|^|M_i| steps
[ checkable in polynomial time w.r.t. |x| ]
if such i exists simulate M_i on input x
until it stops and accept/reject according to its output
or until it reaches 2^|x| steps and in this case reject;
if such i doesn't exist loop for 2^|x| steps and reject.
If $P =NP$ the algorithm will soon or later - suppose on input $x_0$ - find the index of the polynomial time Turing machine (or a padded version of it) $M_{SAT}$ that solves SAT in $O( |x| ^ { |M_{SAT}| })$ and for all inputs greater than $x_0$ will continue to simulate it and halt in polynomial time (note that step 2 can also be checked in polynomial time). In other words if $P = NP$ the algorithm solves SAT in polynomial time on all but a finite number of instances.
If $P \neq NP$ the algorithm runs in exponential time.
answered Oct 19, 2018 at 17:00
-
$\begingroup$ How do I quicly decide if "I is a valid encoding of a proof of P = NP in PA (or ZFC)" ? $\endgroup$ Commented Oct 19, 2018 at 17:03
-
$\begingroup$ @user2925716 You can do it in polynomial time (imagine that $I$ is a string that represents the full proof in any reasonable deduction system). $\endgroup$ Commented Oct 19, 2018 at 18:00
-
2
-
1$\begingroup$ If P≠NP, the runtime of the unconditional algorithm is superpolynomial (as requested), but if NP is only very slightly superpolynomial, not exponential. We can change the algorithm to make it i.o.-exponential, but provably making it exponential (as opposed to just i.o.-exponential) if P≠NP is likely as hard as solving P=NP. $\endgroup$ Commented Oct 20, 2018 at 3:42
-
1$\begingroup$ I used i.o.-exponential to mean exponential for infinitely many input sizes; i.o.-exponential can still oscillate between exponential and non-exponential as input size changes. Also, Emil Jeřábek's comment appears correct; a fix to provably get superpolynomial time (if P≠NP) is to always use at least $x^{|M_i|}$ time; and for i.o.-exponential -- at least $2^x$ each time we increase i. $\endgroup$ Commented Oct 22, 2018 at 15:19