2
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – John Colanduoni Jul 7 '15 at 5:16
  • $\begingroup$ 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. $\endgroup$ – calculemur Jul 7 '15 at 6:30
  • 1
    $\begingroup$ 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. $\endgroup$ – John Colanduoni Jul 7 '15 at 6:47
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ That's an excellent point; I didn't consider such degenerate cases in which counting arguments alone would suffice to determine the possibility of satisfaction. $\endgroup$ – calculemur Jul 7 '15 at 22:55
  • $\begingroup$ Do you have a proof or citation that all NP-complete problems are downward self-reducible? $\endgroup$ – Jonas Kölker Mar 20 '17 at 7:56
  • $\begingroup$ @JonasKölker To my considerable surprise, I don't. It seems to be true for "natural" problems, but I know of no general proof so I will remove that claim. $\endgroup$ – Kyle Jones Mar 20 '17 at 19:01
  • $\begingroup$ 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. $\endgroup$ – Jonas Kölker Mar 21 '17 at 15:01

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.