Editing P versus NP problem (section)

==Polynomial-time algorithms==
No known algorithm for a NP-complete problem runs in polynomial time. However, there are algorithms known for NP-complete problems that if P&nbsp;=&nbsp;NP, the algorithm runs in polynomial time on accepting instances (although with enormous constants, making the algorithm impractical). However, these algorithms do not qualify as polynomial time because their running time on rejecting instances are not polynomial. The following algorithm, due to [[Leonid Levin|Levin]] (without any citation), is such an example below. It correctly accepts the NP-complete language [[subset sum problem|SUBSET-SUM]]. It runs in polynomial time on inputs that are in SUBSET-SUM if and only if P&nbsp;=&nbsp;NP:

 ''// Algorithm that accepts the NP-complete language SUBSET-SUM.''
 ''//''
 ''// this is a polynomial-time algorithm if and only if P = NP.''
 ''//''
 ''// "Polynomial-time" means it returns "yes" in polynomial time when''
 ''// the answer should be "yes", and runs forever when it is "no".''
 ''//''
 ''// Input: S = a finite set of integers''
 ''// Output: "yes" if any subset of S adds up to 0.''
 ''// Runs forever with no output otherwise.''
 ''// Note: "Program number M" is the program obtained by''
 ''// writing the integer M in binary, then''
 ''// considering that string of bits to be a''
 ''// program. Every possible program can be''
 ''// generated this way, though most do nothing''
 ''// because of syntax errors.''
 FOR K = 1...∞
   FOR M = 1...K
     Run program number M for K steps with input S
     IF the program outputs a list of distinct integers
       AND the integers are all in S
       AND the integers sum to 0
     THEN
       OUTPUT "yes" and HALT

This is a polynomial-time algorithm accepting an NP-complete language only if P&nbsp;=&nbsp;NP. "Accepting" means it gives "yes" answers in polynomial time, but is allowed to run forever when the answer is "no" (also known as a ''semi-algorithm'').

This algorithm is enormously impractical, even if P&nbsp;=&nbsp;NP. If the shortest program that can solve SUBSET-SUM in polynomial time is ''b'' bits long, the above algorithm will try at least {{math|2<sup>''b''</sup> − 1}} other programs first.