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

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.

• The formal definition of $P$ requires a mere (correct) yes-or-no answer, so the possibility that a problem in $P$ may require more than polynomial time to find a witness of the result is not immediately ruled out. In general, there are algorithms that use such ad-hoc methods to answer decision problems; the AKS primality test provides a yes or no answer without a witness of primality. However primality is not believed to be NP-complete. – John Colanduoni Jul 7 '15 at 5:16
• What is a "witness to primality"? I'm aware of the term "witness to compositeness" regarding numbers that fail to satisfy Fermat's Little Theorem in association with the number being tested for primality. Is it related? And thanks, you have put forward a very interesting point regarding AKS. – calculemur Jul 7 '15 at 6:30
• Yes, it is precisely the opposite. A witness to primality would be a proof of some property that only primes have. The most trivial one would be the results of division by all integers less than the number. AKS almost provides a (different) witness of primality, but its polynomial running time relies on a proof that it (in essence) doesn't have to check all cases of the property. – John Colanduoni Jul 7 '15 at 6:47

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".
• cs.umd.edu/~samir/grant/self.pdf shows that planar 4-colorability is not self-reducible unless $P = NP$, by showing that finding the lexicographically first 4-coloring is NP-hard—and this is despite planar 4-colorability being in $P$. Of course, this doesn't disprove that all natural NP-complete problems are self-reducible, but this article might be relevant to your interests. – Jonas Kölker Mar 21 '17 at 15:01