[Solved]: Are all known algorithms for solving NP-complete problems constructive?

Problem Detail: 

Are there any known algorithms that correctly output "yes" to an NP-complete problem without implicitly generating a certificate?

I understand that it is straightforward to turn a satisfiability oracle into a satisfying-assignment finder: just iterate over the variables, each time asking the satisfiability oracle to solve the conjunction of that variable with the original problem.

But would such a wrapper ever be useful? Do all sat solvers search over the space of possible assignments?

Or are there some types of NP-complete problems (traveling salesman, subset sum, etc.) in which the solver can, say, exploit a mathematical theorem to prove that a solution must exist? Like doing a proof by contradiction?

Asked By : user82928

Answered By : Juho

As I understand it, you are asking two questions: (1) are there e.g. SAT algorithms that are more clever than naive brute force, and (2) are there algorithms that simply give a YES/NO answer when solving an NP-complete problem without actually finding the solution. I'll answer both questions in this order.

(1) It is perfectly possible to solve a problem without brute force, i.e. without naively trying all possibilities. To take your example, modern complete SAT solvers can apply clever algorithms that infer or prove certain (partial) assignments can't lead to a solution, so they don't even examine that part.

More generally, even NP-hard problems often exhibit some kind of algorithmic foothold that allows us to design algorithm faster than brute force. The field of this research is exact (exponential) algorithms. Such algorithms take exponential time, but are still faster than naive algorithms. For instance, you can solve TSP in roughly $n!$ time, where $n$ is the number of cities to visit. This method won't scale to even moderate values of $n$, but there is a classic dynamic programming $O(2^nn^2)$ time algorithm due to Held & Karp. For general techniques, see e.g. branch & bound.

(2) There are "oracle algorithms" for NP-complete problems that just output YES/NO with no explicit certificate. For instance, consider the $k$-path problem:

(The $k$-path problem) Given a graph $G$ and an integer $k$, is there a simple path in $G$ on $k$ vertices?

The above problem is easily seen to be NP-complete. An $O^*(2^k)$ algorithm for the problem is given in [1]. The algorithm itself only gives a YES/NO answer to the problem, but we can use additional tricks to construct the actual $k$-path itself. More generally, when given such an "oracle algorithm", one can use tools from combinatorial group testing for extracting the witness itself.

---

[1] Williams, Ryan. "Finding paths of length $k$ in $O^*(2^k)$ time." Information Processing Letters 109.6 (2009): 315-318. publisher link, PDF

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/30532