14
\$\begingroup\$

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 ; 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.

\$\endgroup\$
  • 3
    \$\begingroup\$ @EmbodimentofIgnorance Why do you think this a duplicate? There is a restriction here that makes pretty much none of the answers on the other question valid here. \$\endgroup\$ – Ad Hoc Garf Hunter Apr 5 '19 at 18:04
  • \$\begingroup\$ If someone claims she has an algorithm (i.e. constructive proof) and publishes a non-constructive proof instead, no one will believe her \$\endgroup\$ – Luis Mendo Apr 5 '19 at 18:08
  • 1
    \$\begingroup\$ This isn't even close to a duplicate. How do I get this reopened? \$\endgroup\$ – Lopsy Apr 5 '19 at 21:18
  • 1
    \$\begingroup\$ @Lopsy Only if 5 people vote for it to be reopened. I don't think this is a duplicate, but I don't think it's a particularly well-formed prompt. There are glaring issues with it that I think required more time in the Sandbox. \$\endgroup\$ – Don Thousand Apr 5 '19 at 22:17
  • 11
    \$\begingroup\$ I hammered this open. This isn't at all a dupe of the general subset sum challenge since the complexity restriction means none of the answers on the other question come even close to working, nor can they possibly unless P=NP. Answers to this will be very very different. \$\endgroup\$ – xnor Apr 5 '19 at 22:20
3
\$\begingroup\$

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:

enter image description here

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)

|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ This looks like a great effort. Now..... is it correct? :) \$\endgroup\$ – Anush Nov 2 '19 at 12:46
  • \$\begingroup\$ @Anush The three things to be convinced of are (1) it doesn't crash (2) it eventually finds a polynomial time program (3) it does so in polynomial time. I'm pretty sure 2 is right since While is Turing complete; I'm fairly sure 1 is right, since I can't see how to do anything bad without . or alphabetic characters (apart from while); and I'm mostly sure 3 is right, as I can't imagine anything I've used in the program being non-polynomial. Still, for a formal proof you'd need to prove the CPython implementation of the parser and various built ins! \$\endgroup\$ – Uri Granta Nov 2 '19 at 12:54
  • 1
    \$\begingroup\$ I think While alone is not enough. The problem is that the language has so primitive arithmetic that although it is Turing-complete, it requires exponential time to do stuff, e.g. testing A < B requires something like brute force incrementing until you find the smallest number. However, I think your Python fragment works, because you also have efficient mutable lists. \$\endgroup\$ – Ørjan Johansen Nov 2 '19 at 22:35
  • 1
    \$\begingroup\$ Actually, I think adding < to the fragment might fix that, assuming that doesn't make it unsafe. (I think that's also generally enough to make While not exponentially-blowing-up.) \$\endgroup\$ – Ørjan Johansen Nov 2 '19 at 23:12
  • 1
    \$\begingroup\$ Yeah I think everything is polynomial that should be. My reasoning is a bit quirky: using < and repeated doubling you can search for the largest bit in a number, or a difference of numbers. Repeat until you have all the bits. And repeated doubling allows you to turn a list of bits back into a number. \$\endgroup\$ – Ørjan Johansen Nov 3 '19 at 21:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.