Polytime algorithm for SUBSET-SUM assuming P=NP

In the Wikipedia page on P vs. NP problem there is an algorithm that "solves" SUBSET-SUM in case P=NP in polynomial time. (It's idea is to find a TM that gives a certificate). But it gives "yes" in polynomial time and runs forever if the answer is "no". It can be obviously fixed to give "no" in exponential time (just to run exponential algorithm if the first one is running for too long).

But can we explicitly describe an "honest" algorithm, which solves (and I mean, really solves) SUBSET-SUM (or any other NP-complete problem) in polynomial time assuming P=NP?

By "honest" and "really solves" I mean that the algorithm meets the classical definitions for a polynomial-time algorithm, i.e., here should exist constants $C_1, C_2$ such that at any input $x$ algorithm would terminate in no more than $C_1 \cdot |x|^{C_2}$ steps and output "yes" if $x \in $ SUBSET-SUM and "no" otherwise. The Wikipedia algorithm does not satisfy the first condition, so it doesn't "really solve" the problem.

Thefacetakt

Posted 2016-12-18T01:50:18.510

Reputation: 81

I believe this is unknown. The area is known as optimal heuristic algorithms. One of the main researchers is Edward A. Hirsch.

– Yuval Filmus – 2016-12-19T19:47:09.417

@djechlin is right, and Wikipedia is wrong: The algorithm $W$ always halts, because it will eventually hit upon a brute force method, and solve the problem. Moreover, since it is dovetailing all programs, its running time is easily analyzed, too: if on input $x$, the $a$-th algorithm gives an answer in $t$ steps, then $W$ will have simulated $\Theta((a+t)^2)$ steps in total, independent of any complexity-theoretic assumptions; it is true no matter the true complexity of SUBSET-SUM. This method of search is called Levin Search, sometimes Universal Search. – Lieuwe Vinkhuijzen – 2017-05-19T21:38:27.063

Answers

I can half-answer this, but I believe the deeper question you are getting at is something I am in the process of learning better :)

The algorithm on wikipedia, call it W, is based on the idea: rather than guess at certificates why not just guess at the deterministic P algorithm D itself? This is expensive, but since it is independent of the input it is O(1) (if such an algorithm exists). The algorithm actually always decides even if P != NP, because there is of course a series of "brute force" programs that print out just one possible certificate then halt, so W can fall back to a very slow brute force.

The problem is that you actually have no way to verify the program it returns to you. You may imagine running W and find it seems to prefer a certain program, but you may find that on larger input it eventually finds a flaw in that program and moves on. It may seem to settle on an algorithm that seems to be $n^7$ but later on find a mistake in it and switch to an $n^{2000}$ algorithm. You will never know when it has found the "right" one.

This is actually the same idea used in the proof of the Karp-Lipton theorem: given enough computation power you can use it to just start guessing entire classes of programs and verify that they work (the proof is exactly, "guess a program, and verify that it works, then use it", which takes a bit of computational power - more than NP - to pull off.)

I am not aware of theory regarding how complicated a solution can be, but perhaps someone more knowledgeable can answer.

The more concrete scenario in the P=NP reality is that someone actually constructs an algorithm to any NP-complete problem, such as SAT.

I think you asked a good question and I'm curious how to fill in the gaps in my answer, regarding how W may be analyzed and made more useful in semi-practice.

djechlin

Posted 2016-12-18T01:50:18.510

Reputation: 477

Good answer! +1. There is a subtle difference between this search and Karp-Lipton: here, we only have to verify the solution that the program gives; in the Karp-Lipton theorem, you have to verify that the program is correct (for all $x\in {0,1}^\star$) – Lieuwe Vinkhuijzen – 2017-05-19T21:45:50.270

-1

I'll try a partial answer to your question, but I think it should be enough for your quest.

Being NP-complete resorts to being NP AND NP-HARD.

Being NP-HARD means every problem in NP could be translated, via a polynomial time transformation, into this problem.

SSP is know to be NP-HARD (and NP-COMPLETE).

This means, for instance, that you could look-up in the internet, for the specific Polynomial-Time transformation that SHOWS that SSP is NP-HARD (on any paper that proves it).

That transformation is an "honest" algorithm, is guaranteed to run in Polynomial-time, and is written in some paper, somewhere. Let's call it 'SSP-T' (for SSP transformation).

The only way to prove that P=NP is to EXHIBIT an polynomial-time algorithm for a problem in NP.

So if you assume that P=NP, you are assuming YOU HAVE IN YOUR VERY OWN HANDS an "honest" polynomial-time algorithm for solving one (any-one) NP problem. Let's call that algorithm: 'H'

Now... given any problem in NP, let's call it 'My-NP-problem'...

The Solution you are looking for is:

Apply SSP-T to transform it into an instance of SSP,
Now use SSP-T again to transform this SSP instance into an instance of 'H' (the ONE --any-one-- problem NP that YOU KNOW how to solve in P --based on the assumption that P=NP--),
Run H to find a solution.
Use SSP-T to interpret the solution under SSP
Use SSP-T once more to interpret the solution under 'My-NP-problem' (the arbitrary problem you wanted to solve in the beginning).

And there you go!

These 5 sequential steps are the "honest" algorithm you were looking for.

Each step runs in polynomial time and is guaranteed to exist by the very definition of each concept.

You could have chosen any other NP-HARD problem, instead of SSP, because the definition of NP-HARD is the one that guarantees (by definition!) that:

SSP-T exists,
is an algorithm,
is bidirectional,
is valid and applies to any NP problem; and
runs in Polynomial-Time

In fact if you look the most usual way to show that any problem is NP-HARD is VIA a transformation into SAT-3, which was one of the first problems to be shown NP-HARD (sometime in the 60s/70s).

Let me know of any weakness you might find in the reasoning/explanation I gave.

Martin Carames Abente

Posted 2016-12-18T01:50:18.510

Reputation: 1

1It's not true that the only way to prove that P=NP is by exhibiting a polytime algorithm for some problem in NP. It's enough to prove that such an algorithm exists. Besides, the OP is looking for a concrete algorithm that can be described right now. – Yuval Filmus – 2016-12-19T06:20:35.917

I guess you are right, only showing the existance of such 'H' (some polynomial-time solution for some specific NP problem) would show that P=NP. Nevertheless – Martin Carames Abente – 2016-12-19T18:13:35.580

(continues last comment)

Nevertheless the 5 steps given remain an actual/concrete algorithm, one of its inputs being 'H'.

Just as SSP-T has as input: the instance of an NP problem (the one to be transformed into an instance or SSP --or vice versa--).

"Run H to find a solution" is a concrete step, when you have H as an input.

On the other hand YF, if OP is expecting a concrete solution based on an existence theorem, you are right.

But I don't think he is expecting that. It'd be similar to expecting a concrete solution of P=NP in wikipedia. – Martin Carames Abente – 2016-12-19T18:37:08.947