16
$\begingroup$

Is there any general technique for proving a problem NOT being NP-Complete?

I got this question on the exam that asked me to show whether some problem (see below) is NP-Complete. I could not think of any real solution, and just proved it was in P. Obviously this is not a real answer.

NP-Complete is defined as the set of problems which are in NP, and all the NP problems can be reduced to it. So any proof should contradict at least one of these two conditions. This specific problem, is indeed in P (and thus in NP). So I am stuck with proving that there is some problem in NP that can't be reduced to this problem. How on the earth can this be proven??

Here is the specific problem I was given on exam:

Let $DNF$ be the set of strings in disjunctive normal form. Let $DNFSAT$ be the language of strings from $DNF$ that are satisfiable by some assignment of variables. Show whether or not $DNFSAT$ is in NP-Complete.

$\endgroup$
  • 8
    $\begingroup$ If DNF-SAT could be proven not to be NP-complete, it would immediately imply that $P\neq NP$, as you have shown. Thus, I believe the answer they were looking for is exactly what you gave (and you were probably supposed to implicitly assume that $P\neq NP$). Still, this is a very misleading question. $\endgroup$ – Shaull Jun 21 '13 at 11:02
  • $\begingroup$ You are right, so I understand that this problem is equivalent to the problem of $P=NP$ and a solution to one, also solves the other. $\endgroup$ – Untitled Jun 21 '13 at 11:26
  • $\begingroup$ Why do you say of proving that DNFSAT is in P that "obviously this is not a real answer"? $\endgroup$ – András Salamon Jun 21 '13 at 13:32
  • 5
    $\begingroup$ @AndrásSalamon It assumes that $P\neq NP$, which is an unproved statement. $\endgroup$ – Untitled Jun 21 '13 at 15:08
  • 1
    $\begingroup$ @Untitled: it actually does not assume P≠NP, see my answer. $\endgroup$ – András Salamon Jun 23 '13 at 16:25
8
$\begingroup$

Based on the comments, you seem to want an unconditional answer.

However, DNF-SAT is in L, by assigning variables to satisfy the first disjunct. Hence if it is NP-complete, then L=NP.

On the other hand, if L = NP then DNF-SAT is NP-complete under logspace reductions, trivially. (In fact, if L=NP then every problem in NP is NP-complete under logspace reductions.)

It follows that L=NP iff DNF-SAT is NP-complete under logspace reductions.

So you cannot currently make an unconditional statement that DNF-SAT is not NP-complete, as you seem to want to do. It is not necessary to assume P≠NP, but the answer does have to be conditional on something, and L≠NP is the weakest possible hypothesis that guarantees the desired result.

$\endgroup$
  • $\begingroup$ Interesting. So this problem is equivalent to the problem of $L=NP=P=NPC$. Could you explain why you say $L\neq NP$ is a weak assumption? $\endgroup$ – Untitled Jun 24 '13 at 3:19
  • 3
    $\begingroup$ If $\phi \Rightarrow \psi$ then $\psi$ is weaker than $\phi$. $\endgroup$ – András Salamon Jun 24 '13 at 7:39
14
$\begingroup$

A problem $Q$ is NP-complete if it is both NP-hard and in NP. This means that you need to disprove one of these two.

  1. Under the assumption that P $\neq$ NP, you can give a polynomial time algorithm solving $Q$. Rarer, under the assumption that graph isomorphism is not NP-hard, you can show that $Q$ is polytime reducible to graph isomorphism.
  2. You show that $Q$ is not in NP. This is harder, and you must usually use other assumptions, like non-collapse of polynomial hierarchy, that NP $\neq$ coNP or show that it is hard for some other class higher than NP, e.g. by showing that it is NEXPTIME-hard.

Usually, the answer is to give a polynomial time algorithm, which would be the simplest for DNF-SAT, but this relies on the hypothesis that P $\neq$ NP. However, proving that DNF-SAT is not NP-complete without any assumptions implies, as Shaull points out, proving that P $\neq$ NP, so that is somewhat trickier.

$\endgroup$
  • 1
    $\begingroup$ Both the techniques you provided lie on some kind of unproved assumption. Do think there could be a concrete way (no assumptions) of solving a problem of this kind? $\endgroup$ – Untitled Jun 21 '13 at 11:22
  • $\begingroup$ Oh, and I didn't mean this specific problem, because as Shaull stated, this problem is still open. I meant proving coNP-Completeness in general. $\endgroup$ – Untitled Jun 21 '13 at 11:28
  • 2
    $\begingroup$ @Untitled You probably didn't mean coNP-completeness. One way of showing it is by my point (2), proving that the problem is NEXPTIME-hard. We know that NP $\subsetneq$ NEXPTIME, so that would prove it. Proving that a problem $Q$ is NEXPTIME-hard, would therefore mean that $Q$ cannot be in NP and thus cannot be NP-complete. $\endgroup$ – Pål GD Jun 21 '13 at 11:52
10
$\begingroup$

By the nondeterministic time hierarchy, you could show that the problem is $\mathsf {NEXP}$-hard; as $\mathsf {NP} \ne \mathsf {NEXP}$, it is impossible to reduce the problem in polynomial time to any problem in $\mathsf {NP}$, so the problem will not be in $\mathsf {NP}$.

However, if your problem is not nearly that difficult, you may be hard-pressed to prove that it is not in $\mathsf {NP}$; and if it is in $\mathsf {NP}$, you'll be hard-pressed to show that $\mathsf {NP}$ is not Karp-reducible to your problem without assuming that $\mathsf P \ne \mathsf {NP}$.

$\endgroup$
0
$\begingroup$

As is the case with all proofs, there is no formula for proving a statement, you have to do some intelligent guesswork, trial and error and hopefully you'll be able to prove what you are trying to prove. To prove a problem is NOT NP-Complete, negate the definition (DeMorgran Law), that is to say prove the problem NOT in NP or prove the problem NOT NP-Hard.

$\endgroup$
0
$\begingroup$

I believe what the lecturer really wants is that you could distinguish problems that are in P from problems that are NP-complete in the meaning given language can you build an efficient algorithm ? if yes then it is suspected not to be NP-complete because we dont think that languages in P is NP-complete ! otherwise you still have to prove that the problem is NP-hard !

note that there exists some problems that we dont know there status such as graph isomorphism,factoring given number,... we think that these problems are not NP-complete but no one could prove that ! specifically we have evidences that graph isomorphism is not NP-complete! other problem is the unique game conjuncture that we suspect that unique game is NP-complete but no proof exists! so the approach you have describe is not helpful!

$\endgroup$

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.