Shocking news: Dr. Mad J Scientist has released a proof of P = NP to the world. But the proof is nonconstructive, and she's keeping the algorithm to herself.
Worry not. Without even looking at her proof, we can still (almost) write a computer program that solves NP-complete problems in polynomial time.
Input a list of integers, such as
[-10, -4, 1, 1, 2, 6, 8]. Output a nonempty sublist that sums to 0, such as
[-10, 1, 1, 2, 6]. The output list can be in any order. Ignore any integer overflow issues in your language.
If P = NP, your program must provably run in polynomial time on solvable inputs. Your program may act arbitrarily on inputs with no solution. This is code-golf; shortest code wins.
Yes, this challenge is possible. One approach is as follows:
Enumerate all possible computer programs \$P_0, P_1, P_2, \dots\$
Repeat as \$i\$ goes from 0 to \$\infty\$:
----- Run the first \$i\$ programs on the input list, for \$i\$ steps each.
----- For each output you get, check whether it's a valid subset sum solution. If so, return it.
This works because, if P = NP, then some program \$P_m\$ solves subset-sum in some polynomial time \$O(n^k)\$. Therefore, the above algorithm will output a solution on the \$\max(m, O(n^k))\$th iteration of the loop, if not before. Therefore, the above algorithm runs in polynomial time on solvable inputs.
Note: A proof that P ≠ NP would allow a 0-byte solution to this problem. Good luck with that :)
Before you start
evaling all strings in a language like Python, let me point out that some of those strings will reformat your hard drive.
This challenge does not run afoul of the no famous open questions rule, because although it is related to P vs NP, this challenge is solvable.