I have an NP-complete decision problem. Given an instance of the problem, I would like to design an algorithm that outputs YES, if the problem is feasible, and, NO, otherwise. (Of course, if the algorithm is not optimal, it will make errors.)

I cannot find any approximation algorithms for such problems. I was looking specifically for SAT and I found in Wikipedia page about Approximation Algorithm the following: Another limitation of the approach is that it applies only to optimization problems and not to "pure" decision problems like satisfiability, although it is often possible to ...

Why we do not, for example, define the approximation ratio to be something proportional to the number of mistakes that the algorithm makes? How do we actually solve decision problems in greedy and sub-optimal manner?

  • 5
    $\begingroup$ There are approximation algorithms for MAX-SAT. $\endgroup$ – Yuval Filmus Nov 7 '16 at 23:45
  • 2
    $\begingroup$ MAX-SAT is not a decision problem, no? $\endgroup$ – Ribz Nov 7 '16 at 23:45
  • 15
    $\begingroup$ Approximation algorithms are always for optimization problems. $\endgroup$ – Yuval Filmus Nov 7 '16 at 23:46
  • 4
    $\begingroup$ So you basically want to have an algorithm that finishes quickly but is allowed to occasional give the wrong answer. I think you are confusing issues hugely by using well-defined terms like "approximation algorithm" and "optimal" here. Those have very specific meanings. I guess you are looking for a heuristic instead - if you update your question with that term (or start from scratch with a new question to avoid even more confusion), you might have better results. $\endgroup$ – AnoE Nov 8 '16 at 17:29
  • $\begingroup$ While this isn't a complete answer, it explains part of the reason: there exist important SAT problems for which having only the low bit wrong is no better than being half the bits wrong. $\endgroup$ – Joshua Nov 8 '16 at 19:40

Approximation algorithms are only for optimization problems, not for decision problems.

Why don't we define the approximation ratio to be the fraction of mistakes an algorithm makes, when trying to solve some decision problem? Because "the approximation ratio" is a term with a well-defined, standard meaning, one that means something else, and it would be confusing to use the same term for two different things.

OK, could we define some other ratio (let's call it something else -- e.g., "the det-ratio") that quantifies the number of mistakes an algorithm makes, for some decision problem? Well, it's not clear how to do that. What would be the denominator for that fraction? Or, to put it another way: there are going to be an infinite number of problem instances, and for some of them the algorithm will give the right answer and others it will give the wrong answer, so you end up with a ratio that is "something divided by infinity", and that ends up being meaningless or not defined.

Alternatively, we could define $r_n$ to be the fraction of mistakes the algorithm mistakes, on problem instances of size $n$. Then, we could compute the limit of $r_n$ as $n \to \infty$, if such a limit exists. This would be well-defined (if the limit exists). However, in most cases, this might not be terribly useful. In particular, it implicitly assumes a uniform distribution on problem instances. However, in the real world, the actual distribution on problem instances may not be uniform -- it is often very far from uniform. Consequently, the number you get in this way is often not as useful as you might hope: it often gives a misleading impression of how good the algorithm is.

To learn more about how people deal with intractability (NP-hardness), take a look at Dealing with intractability: NP-complete problems.

  • 3
    $\begingroup$ +1. But the last point is not solid, one could argue that you can define the approximation ratio as the limit as n goes to infinity of the number of mistakes the program makes on input of length n over the number of strings of length n. This of course turns out to be not useful, as often a simple program that just outputs "YES" (or "NO") achieves a good ratio (sometimes even 1!). $\endgroup$ – aelguindy Nov 7 '16 at 23:54
  • 1
    $\begingroup$ @det, that's a separate question, one that you should ask separately (after reading about it in standard textbooks or online resources). We prefer that you ask only one question per post. $\endgroup$ – D.W. Nov 7 '16 at 23:55
  • 1
    $\begingroup$ @aelguindy, good point. I've updated my answer accordingly. $\endgroup$ – D.W. Nov 7 '16 at 23:57
  • 2
    $\begingroup$ @det Why greedy? What does it mean to "almost" solve a decision problem? $\endgroup$ – Raphael Nov 8 '16 at 0:30
  • 2
    $\begingroup$ @Mehrdad: Usually you evaluate an approximation algorithm by its worst-case error: an upper bound on how non-optimal it ever is. So, for example, you might say that a given approximation algorithm always finds a result that is at least five-sixths of the optimal result. There's no real way to translate that to a decision problem; if your algorithm sometimes emits (say) 0.1, then either it's sometimes off by 0.9 (in which case you would do better, in the worst case, to always emit 0.5), or the "approximate"-ness is a sham and "0.1" actually just means "0". $\endgroup$ – ruakh Nov 8 '16 at 6:37

The reason you don't see things like approximation ratios in decision making problems is that they generally do not make sense in the context of the questions one typically asks about decision making problems. In an optimization setting, it makes sense because it's useful to be "close." In many environments, it doesn't make sense. It doesn't make sense to see how often you are "close" in a discrete logarithm problem. It doesn't make sense to see how often you are "close" to finding a graph isomer. And likewise, in most decision making problems, it doesn't make sense to be "close" to the right decision.

Now, in practical implementations, there are many cases where it's helpful to know what portion of the problems can be decided "quickly" and what portion cannot. However, unlike optimization, there's no one-size-fits-all way to quantify this. You can do it statistically, as you suggest, but only if you know the statistical distribution of your inputs. Most of the time, people who are interested in decision problems are not so lucky to have such distributions.

As a case study, consider the halting problem. The halting problem is known to be undecidable. It's a shame, because its a really useful problem to be able to solve if you're making a compiler. In practice, however, we find that most programs are actually very easy to analyze from a halting problem perspective. Compilers take advantage of this to generate optimal code in these circumstances. However, a compiler must recognize that there is a possibility that a particular block of code is not decidable. Any program which relies on code being "likely decidable" can get in trouble.

However, the metric used by compilers to determine how well they do at solving these particular cases of the halting problem is very different from a metric used by a cryptography program to test whether a particular pair of primes is acceptably hardened against attacks. There is no one size fits all solution. If you want such a metric, you will want to tailor it to fit your particular problems space and business logic.

  • $\begingroup$ So, as I understand, the only way to solve a decision problem is to design the optimal algorithm which may be very inefficient? Because I have a decision problem (NP-complete) and I was asked to come up with a greedy (fast) algorithm to find a solution. How can I solve this? Do you know of any paper that focuses on this kind of problems? $\endgroup$ – Ribz Nov 8 '16 at 16:30
  • 1
    $\begingroup$ @det Push back and get the problem restated. If you have a NP-complete problem, you're rather stuck, but its highly likely that you don't actually need to solve one. For example, you don't always need the perfect answer. Maybe close is good enough. Or maybe you can solve the problem for a subset of cases which are easy, and punt on the ones that are hard. As an example, packing algorithms are often NP-complete, but algorithms which reliably get within 5% of optimal using probabalistic approaches are common. $\endgroup$ – Cort Ammon Nov 8 '16 at 18:18
  • 2
    $\begingroup$ In all honesty, being told to come up with a greedy algorithm to solve a NP-complete program is literally the same as being tasked to take on the entire computer science/mathematical community singlehandedly. If you find an algorithm for a NP-complete program in P time, at the very least you would earn the $1million Clay prize for solving P=NP. In reality, the effects of your discovery would reshape computing as we know it, and completely upheave the entire security/cryptography industry overnight. Better to have the wording of the task adjusted to not be provably NP-complete. $\endgroup$ – Cort Ammon Nov 8 '16 at 19:09
  • $\begingroup$ I have used a greedy exact algorithm for an NP-complete problem. I only needed to solve a small case, and I could get a 64-processor server for a weekend. $\endgroup$ – Patricia Shanahan Nov 9 '16 at 16:44

In addition to the existing answers, let me point out that there are situations where it makes sense to have an approximate solution for a decision problem, but it works different than you might think.

With these algorithms, only one of the two outcomes is determined with certainty, while the other might be incorrect. Take the Miller-Rabin test for prime numbers, for instance: If the test determines that a number is not prime, that result is for certain. But in the other case it only means that the number is probably prime. Depending on how much compute time you are willing to invest, you can increase your confidence in the result, but it won't be 100% as it is for the not-prime case.

This is especially powerful when tackling undecidable problems: You could write a tool that tries to solve the halting problem for a specific piece of code. If it can find a proof that the program will not loop endlessly, you can claim so with 100% certainty. If you cannot find such a proof, it might just be that the program control flow is too convoluted for your tool to analyze, but it is not a proof that it will loop forever. By simplifying the control structures, you might be able to create an equivalent program that is simple enough for the tool to proof that it will halt for certain.

  • $\begingroup$ There is a big difference between probabilistic (your answer) and approximation (the question) algorithms. In particular, the combination of both is a very special breed. $\endgroup$ – Raphael Nov 8 '16 at 16:27
  • $\begingroup$ Also, we know that probabilistic algorithms for the halting problem don't exist, assuming a reasonable interpretation of the term in this context. $\endgroup$ – Raphael Nov 8 '16 at 16:30
  • $\begingroup$ @Raphael I did not intend my answer to be specific to probabilistic algorithms. Granted, for Miller-Rabin that is the case, but as you mentioned yourself, this is no longer true for the halting problem example, and I guess also won't be true for the majority of cases where you find this behavior. The point I wanted to get across is simply that you will only get certainty on one outcome, but not on the other. $\endgroup$ – ComicSansMS Nov 8 '16 at 16:50
  • $\begingroup$ If you're not saying more than that some problems are only semi-computable, I don't think you are answering the question. $\endgroup$ – Raphael Nov 8 '16 at 16:55
  • $\begingroup$ @Raphael My answer is also not specific to semi-computable problems. In fact, I don't think the approach I described even applies to semi-computable problems. There you will now for sure if you landed in the undefined branch of the function, so you can claim with certainty that there is no result. What I described boils down to: There might be an answer, but the algorithm might not have looked hard enough to stumble over it. $\endgroup$ – ComicSansMS Nov 8 '16 at 18:09

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.