Solve Subset-Sum in polynomial time (...if P = NP)

Question

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.

The Problem

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 :)

Notes

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.

Answer 1

Python 3.8 (on Unix), 429 bytes

Since nobody else has posted an answer yet, I thought I'd have a go, though I not 100% certain I haven't missed something important (and I am 100% certain the code could be shrunk down significantly).

As noted in the question, evaluating arbitrary Python strings is dangerous. Fortunately, it's easy to come up with a safe subset of strings whose evaluation is still Turing complete, by embedding the Turing complete While Programming Language, summarised below:

This can be embedded into Python using only strings that match the following regex:

^([0-9 \n():_=+-]|while)+$

To reduce the number of necessary characters, we use a few embedding hacks:

• variable names are built only of underscores
• if B then C1 else C2 is emulated using while loops (and temporary variables x and y, which hang around afterwards but that's ok):

x=B;y=not x
while x:C1;x=False
while y:C2;y=False

• skip is emulated using any constant expression, e.g. 0
• true is emulated using e.g. 0==0
• false is emulated using e.g. 0==1
• B & C is emulated using a pre-evaluated if-then-else (and another temporary variable x):

if B then x=C else x=False

• ¬ B is emulated using 1-B

To make our life easier, we also allow [ and ], as this permits direct operations on lists (including slicing and concatenation) which avoids having to translate the problem from one on lists into one on integers.

Update: as noted by @ØrjanJohansen, it's also necessary to include < to ensure basic arithmetic remains polynomial.

I claim that any program with just those characters will either execute, or (far more likely) fail to execute, or raise an exception, but will not crash the interpreter or change any global state. Please correct me if I'm wrong.

The rest of the solution is now similar to the prototype presented in the question. We generate all strings of increasing lengths n and execute them, prepopulating the input in variable _ and checking and validating any output from the same variable. We catch any raised exceptions and continue.

The main tricky bit is ensuring polynomial complexity (and termination). We do this by breaking out of each execution after n seconds, using Unix signals and a handler that raises an exception (which the string executions themselves have no way of catching). Since every program will appear repeatedly (eg with trailing whitespace), we don't need to worry about breaking out too soon from a correct program. One tricky bit here is to make sure that the program doesn't crash if the signal is received after the execution completed (successfully or not) but before the signal has been reset; this explains the nested try-catch.

from itertools import*
from re import*
from signal import*
I=eval(input())
signal(SIGALRM,0)
for n in count():
 for p in product(*[set(map(chr,range(128)))]*n):
  if match("([0-9 \n()[\]:_=<+-]|while)+$",(s:="".join(p))):
   try:
    try:
     g={'_':I[::]};alarm(n);exec(s,g);h=g['_']
     if h and all(h.count(x)<=I.count(x)for x in h)and sum(h)==0:
      print(h);n=-1;break
    except:0
    alarm(0)
   except:0
 if n<0:break

Try it online! (though don't expect an actual result; it may be P but it's obscenely slow)