3 ms·

In this context we can divide problems into two cases: optimization problems ("find a solution that satisfies P, in a way that has the highest score") and decis

In this context we can divide problems into two cases: optimization problems ("find a solution that satisfies P, in a way that has the highest score") and decision problems ("is there a solution that satisfies P, with score >= X" or "find a solution that satisfies P, with score >= X"). Complexity classes like NP are defined only for decision problems, not for optimization problems. NP can be defined either as * the set of decision problems where, given a solution, you can check it in polynomial time with a deterministic Turing machine, or * the set of decision problems solvable in polynomial type by a non-determistic Turing machine these two definitions being equivalent. When someone mentions an optimization problem being in P, NP, or NP-hard, they actually mean the associated decision problem being in P/NP/NP-hard. While technically incorrect, this is fine when working informally, because you can "translate" between the two in polynomial time. If I give you an oracle (ie. a magic box) that solves an optimization problem (ie. gives you a solution to P with the highest score) immediately, you can trivially write a polynomial time algorithm that solves the decision problem: call the oracle, check the score of its answer, then compare that with the X value you were given. And vice versa: if I give you an oracle that solves a decision problem immediately (ie. given a value X, gives you a solution satisfying P with score >= X), you can write a polynomial time algorithm that uses the oracle a few times with the right values of X (exponential search then bisection), to find the solution with the highest score.

akoboldfrying 2y ago
Nitpick: Decision problems only have yes/no answers ("is there a solution that satisfies P, with score >= X"); problems that ask for actual solutions with a more complicated structure ("find a solution that satisfies P, with score >= X") are function problems, not decision problems. Interestingly, even though the solution to a decision problem only gives you 1 bit of information, for all NP problems I'm aware of, solving a polynomial number of problem instances is still enough to recover a full solution. For example, suppose we're looking for a maximum clique in a graph. First, binary search as you describe to find the size of the maximum clique. Call that size X. Then to find an actual clique of size X, repeat the following for each vertex v in the graph, in any order: 1. Tentatively delete v and solve the problem "Is there now a clique of size >= X?". 2. If the answer is yes, delete v permanently: we can ignore it from this point on since there is some X-clique that avoids it, and we already know from our initial binary search that that clique is best-possible. 3. If the answer is no, v must belong to every X-clique in the graph. We can't do without it, so reinstate it in the graph. Afterwards, exactly X vertices will remain -- the vertices of some maximum clique in the original graph.

akoboldfrying 2y ago

Nitpick: Decision problems only have yes/no answers ("is there a solution that satisfies P, with score >= X"); problems that ask for actual solutions with a more complicated structure ("find a solution that satisfies P, with score >= X") are function problems, not decision problems. Interestingly, even though the solution to a decision problem only gives you 1 bit of information, for all NP problems I'm aware of, solving a polynomial number of problem instances is still enough to recover a full solution. For example, suppose we're looking for a maximum clique in a graph. First, binary search as you describe to find the size of the maximum clique. Call that size X. Then to find an actual clique of size X, repeat the following for each vertex v in the graph, in any order: 1. Tentatively delete v and solve the problem "Is there now a clique of size >= X?". 2. If the answer is yes, delete v permanently: we can ignore it from this point on since there is some X-clique that avoids it, and we already know from our initial binary search that that clique is best-possible. 3. If the answer is no, v must belong to every X-clique in the graph. We can't do without it, so reinstate it in the graph. Afterwards, exactly X vertices will remain -- the vertices of some maximum clique in the original graph.