5
$\begingroup$

After we prove that a certain optimization problem is NP-hard, the natural next step is to look for a polynomial algorithm that comes close to the optimal solution - preferrably with a constant approximation factor.

After we prove that a certain decision problem is NP-complete, what is the natural next step? Obviously we cannot "approximate" a boolean value...

My guess is that, the next step is to look for a randomized algorithm that returns the correct solution with a high probability. Is this correct?

If so, what probability of being correct can we expect to get from such a randomized algorithm?

As far as I understand from Wikipedia, PP contains NP. This means that, if the problem is in NP, it should be easy to write an algorithm that is correct more than $0.5$ of the times.

However, it is not known whether BPP contains NP. This means that, it may be difficult (if not impossible) to write an algorithm that is correct more than $0.5+\epsilon$ of the times, for every positive $\epsilon$ independent of the size of input.

Did I understand correctly?

$\endgroup$
  • 1
    $\begingroup$ "what is the natural next step?" fixed parameter tractability (FPT) $\endgroup$ – seteropere Jan 2 '14 at 6:35
  • 3
    $\begingroup$ Did you see this question? $\endgroup$ – Raphael Jan 3 '14 at 6:16
8
$\begingroup$

You made a crucial change to the question. I've updated my answer to respond to the new question; I'll keep my original answer below for posterity as well.


To answer the latest iteration of the question: If the problem you really want to solve is a decision problem, and you've shown that it is NP-complete, then you might be in a tough spot. Here are some candidate next steps:

  • Look for heuristics. This means algorithms that work on some problem instances, but not all. Basically, you're hoping that you only come across problem instances that are easy, not any of the worst-case problem instances.

    SAT solvers are an example of this approach. They solve a NP-complete decision problem ("does SAT formula $\varphi$ have a satisfying assignment?") using heuristics that happen to work well on many of the formulas we run into in real life, but their worst-case running time remains exponential. Integer linear programming is another example of this.

    One very powerful kind of heuristic is to formulate your problem as an instance of SAT, ILP, constraint satisfaction programming, or something like that; and then apply an off-the-shelf SAT/ILP/CSP solver to solve it.

  • Look for a fixed-parameter tractable algorithm. Sometimes the complexity of a problem can be characterized by multiple parameters, and occasionally one can find an algorithm that is polynomial in one of the parameters, even if it is exponential in the length of the input (and thus is not a polynomial-time algorithm).

    An example would be the knapsack problem, which takes as input an integer $W$ (the capacity of the knapsack) and some other inputs describing the items you can select from. The knapsack problem is NP-hard. However, there is a standard dynamic programming algorithm whose running time is $O(nW)$. This algorithm is exponential in the length of the input (because $W$ is specified in binary, so the value of $W$ is exponential in the length of the input), and thus this does not qualify as a polynomial-time algorithm. However, if $W$ is not too large -- as will often be the case in many practical settings -- this algorithm is efficient enough nonetheless.

  • Start looking at algorithms whose running time is exponential, or at least super-polynomial. Sometimes the running time can be optimized so that the exponential running time is (just barely) tolerable.

  • Change the problem. Start looking for way which you can "cheat", i.e., change the assumptions or the information given to you to make the computational problem easier.

  • Give up. Accept that this is one problem you probably won't be able to solve.

These are standard strategies for coping with NP-completeness. Many textbooks mention these options.

No, randomization alone is not going to take a NP-complete problem and make it easy to solve in polynomial time. Everyone knows that proving $P\ne NP$ is a famous hard problem, and that most complexity theorists expect that $P \ne NP$ but just don't know how to prove it; similarly, most complexity theorists expect that $BPP \ne NP$, but they just don't know how to prove it. Proving that $BPP \ne NP$ looks even harder than proving that $P \ne NP$. That's why it is the $P \ne NP$ problem that is famous, not the $BPP \ne NP$ problem; if we can't prove that $P \ne NP$, we have no hope of proving that $BPP \ne NP$.

Incidentally, many complexity theorists expect that $P = BPP$, but proving that is way beyond our current knowledge. That said, for all practical engineering purposes, you can assume that $P = BPP$. (Complexity theorists, close your eyes here. I'm about to use some engineering reasoning that works well enough for all engineering purposes, but will drive theorists crazy.) If you have an efficient randomized algorithm that solves some natural real-world problem, I bet I can build a deterministic algorithm that will almost surely solve the problem, too; I won't be able to give you a proof of that fact, but I'll gladly take that bet even at \$100 to \$1 odds in your favor. How can I be so confident? Because if we take your randomized algorithm and, instead of feeding it truly random bits, feed it bits from the output of a cryptographic-strength pseudorandom generator, then there's no way your randomized algorithm is going to be able to tell the difference. After all, if it could, it would have found a way to break the crypto. If you find a way to break the crypto, there are people who will pay you a whole lot more than \$100 for the secret. That's part of the reason why many people expect that $P = BPP$ (or some moral equivalent) is probably true.


Your original question said you wanted to find an approximate solution to a NP-complete problem, and asked what performance is possible. Here was my answer to that question:

It depends on the problem. Some NP-hard optimization problems have good approximation algorithms; others don't. There's lots written in textbooks (and in Wikipedia) on approximation algorithms for NP-hard problems; this is a standard topic in undergraduate algorithms. See, e.g., https://en.wikipedia.org/wiki/Approximation_algorithm and https://en.wikipedia.org/wiki/Polynomial_time_approximation_scheme, but make sure to read textbooks too.

BPP is not a relevant concept here. The question of whether $NP \subseteq BPP$ would be relevant if you were looking for a randomized algorithm that produces an exact solution to the NP-complete problem. But that's not what you're looking for. You're looking for a randomized algorithm that produces an approximate solution to the problem. Looking for an approximate solution is a different problem than looking for an exact solution. If there were a polytime randomized algorithm to find an approximate solution, that wouldn't imply that there's a polytime algorithm to find an exact solution, and it wouldn't imply that $NP \subseteq BPP$. Similarly, if there were a polytime deterministic algorithm to find an approximate solution, that wouldn't imply that there's a polytime algorithm to find an exact solution, and it wouldn't imply that $P=NP$.

Similarly, $PP$ is not very relevant here.

If you really want to relate this to complexity classes, the relevant complexity class is $APX$ (see, e.g., https://en.wikipedia.org/wiki/APX).

Incidentally, many approximation algorithms are deterministic algorithms. Randomization is occasionally helpful but often not needed.

$\endgroup$
  • $\begingroup$ Note that I asked about decision problems - not optimization problems. What is the meaning of "approximate" in a deterministic algorithm for a decision problem? $\endgroup$ – Erel Segal-Halevi Jan 1 '14 at 5:51
  • $\begingroup$ I edited my question to emphasize that it is about decision problems. $\endgroup$ – Erel Segal-Halevi Jan 1 '14 at 11:14
  • $\begingroup$ @ErelSegalHalevi, that wasn't clear to me from the initial question, but OK, I edited my answer to respond to the new question. $\endgroup$ – D.W. Jan 1 '14 at 16:14
  • $\begingroup$ Thanks a lot for the detailed answer, and sorry for the confusion. Just to make sure I got it right: if a decision problem is NP-complete, then it is very unlikely that it is in BPP. Therefore, it is unlikely that I find an algorithm that gives the correct answer with probability 2/3 (or any other constant larger than 1/2). Is this correct? $\endgroup$ – Erel Segal-Halevi Jan 1 '14 at 18:20
  • 1
    $\begingroup$ @ErelSegalHalevi, yes, that's correct! $\endgroup$ – D.W. Jan 1 '14 at 19:41

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.