10
\$\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\$ – Sriotchilism O'Zaic Apr 5 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 at 18:08
  • 1
    \$\begingroup\$ This isn't even close to a duplicate. How do I get this reopened? \$\endgroup\$ – Lopsy Apr 5 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 at 22:17
  • 9
    \$\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 at 22:20

Your Answer

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

Browse other questions tagged or ask your own question.