Is it known whether a hypothetical P-time NP-complete decision procedure has to find a specific solution to the given constraint satisfaction problem?

85 Views Asked by At

Suppose a hypothetical decision procedure $A$ could solve NP-complete problems in polynomial time (of course implying $NP = P$).

Many NP-complete problems take the form of constraint satisfaction, in which the input specifies a given constraint and the decision procedure must determine whether solutions exist or do not.

If $A(I) = true$ for some input value $I$, is it known whether $A$ must actually find a specific solution to the given constraint satisfaction problem specified by $I$? Or is it considered possible that the algorithm could use some (as-yet currently unknown) method to logically infer the existence of one or more solutions without computationally verifying that at least one specific solution satisfies the given constraint?

For example, take the subset sum problem. Must a hypothetical decision procedure actually have to find a given subset and verify that its sum is equal to the required number in order return $true$?

Or can it just analyze the set of numbers in some unknown way and come to the conclusion that such a subset exists without having to identify the particular numbers that add up to the sum.

1

There are 1 best solutions below

4
On BEST ANSWER

A decision procedure for an NP-complete problem need not find a solution. As an example, one decision procedure for 3-SAT is to count the number of assignments explicitly excluded by the CNF clauses. Care has to be taken not to double-count assignments excluded by more than one clause. If the total number of assignments excluded is less than $2^n$ (where $n$ is the number of variables in the formula) then there must be a solution, so the decision procedure answers "yes". If all $2^n$ possible assignments are excluded then the procedure answers "no".

For "yes" answers, any such decision procedure can then be used to find an explicit variable assignment in a polynomial number of invocations. This is because "natural" NP-complete problems like SAT are known to be downward self-reducible.