7
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ I believe this is unknown. The area is known as optimal heuristic algorithms. One of the main researchers is Edward A. Hirsch. $\endgroup$ Dec 19, 2016 at 19:47
  • $\begingroup$ @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. $\endgroup$ May 19, 2017 at 21:38

2 Answers 2

3
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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$) $\endgroup$ May 19, 2017 at 21:45
0
$\begingroup$

I. previously posted another answer (a long time ago), but it had flaws, so I've deleted it.

I gave some extra thought to your question (and Wikipedia's polynomial-time semi-algorithm).

I'll argue here in a similar way to the argument in the 2nd paragraph of @djechlin.

The semi-algorithm there (let's call it W) is an honest semi-algorithm because it shows that actual Cw1 and Cw2 exist (even though it can't show its actual values):

due to the assumption of P==NP, there exists some semi-algorithm (let's call it X), a poly-time semi-algorithm, solving any NP-complete algo (such as SSP)

Even though you don't know X, you can:

  • try each and every number of steps K; and
  • run each and every program, with an index M lower than K on S for K steps (program are enumerable).

(this is the W presented in Wikipedia)

Since X exists and is a semi-algorithm it has a finite length, so its index is a finite number (b bits long).

If there's a solution for S, X will find it in a polynomial number of X-steps.

As @djechlin states, the number of W-steps, finally, depends on:

  • number of X-steps (polynomial on the size of S), and
  • index of X (independent of S)

As such, the index-of-X is O(1) with respect to the size of S.

So, W is a poly-time semi-algorithm.

That time complexity being: (2ˆb - 1) * (Cx1 + Cx2 * size(S))ˆ2

You might try, at most:

  • (2ˆb - 1) programs,

and run each, at most, for:

  • K-steps, from 1 up to the complexity of X (second term)

Using 1 + 2 + ... + n == 1/2 * n * (n + 1) ~ O(nˆ2)

Of course, you don't know Cx1, Cx2, b, but they are proven to exist.

With this, you can see that W is an honest semi-algorithm.

You don't have to look further.

The only caveat is that X and W are semi-algorithms, they answer yes in poly-time when there's a solution and might not halt for S without a solution. But that's already part of the definition of P==NP. The X in the demonstration of P==NP is required to be a semi-algorithm (only has to "accept" a given language in poly-time).

This was quite long, so it should be improved (presented in a more elegant way).

I hope this is correct and clear enough.

$\endgroup$
6
  • $\begingroup$ @YuvalFilmus, if possible, could you proofread my answer looking for any flaw or maybe a suggestion to make it simpler or more elegant? $\endgroup$ Mar 25 at 16:56
  • $\begingroup$ Algorithm X doesn't reveal itself to be a correct algorithm for SUBSET-SUM. Rather, in the YES case, Algorithm X produces the solution, which Algorithm W can verify. For all we know, Algorithm X only works correctly on the instance at hand. There is no known similar NO witness for SUBSET-SUM (the existence of such a witness would imply NP=coNP), so we don't know how to implement this kind of strategy for NO instances. $\endgroup$ Mar 26 at 6:12
  • $\begingroup$ @MartinCaramesAbente, next time, please use the "Edit" button at the bottom of the deleted answer of yours to update it. Once you have finished editing, click "Save edits" button. You can undelete it to make it visible to others. $\endgroup$
    – John L.
    Mar 26 at 22:17
  • $\begingroup$ @JohnL. The new answer was kind of radically different, it wasn't just an edit of the old one. That's why I've deleted and created a new one. Is that ok? $\endgroup$ Mar 30 at 21:44
  • $\begingroup$ @YuvalFilmus Yes, that's right. I'm arguing-about / describing a Semi-Algorithm X, not an algorithm as he asks. This is not an actual answer in that sense. $\endgroup$ Mar 30 at 22:12

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.