21
$\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.

Improve this question
$\endgroup$
5
  • 9
    $\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
    Commented Jun 21, 2013 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
    Commented Jun 21, 2013 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
    Commented Jun 21, 2013 at 13:32
  • 6
    $\begingroup$ @AndrásSalamon It assumes that $P\neq NP$, which is an unproved statement. $\endgroup$
    – Untitled
    Commented Jun 21, 2013 at 15:08
  • 1
    $\begingroup$ @Untitled: it actually does not assume P≠NP, see my answer. $\endgroup$
    – András Salamon
    Commented Jun 23, 2013 at 16:25

6 Answers 6

Reset to default
10
$\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.

Improve this answer
$\endgroup$
2
  • $\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
    Commented Jun 24, 2013 at 3:19
  • 3
    $\begingroup$ If $\phi \Rightarrow \psi$ then $\psi$ is weaker than $\phi$. $\endgroup$
    – András Salamon
    Commented Jun 24, 2013 at 7:39
20
$\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.

Improve this answer
$\endgroup$
3
  • 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
    Commented Jun 21, 2013 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
    Commented Jun 21, 2013 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$
    – John Kemeny
    Commented Jun 21, 2013 at 11:52
13
$\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}$.

Improve this answer
$\endgroup$
2
$\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!

Improve this answer
$\endgroup$
2
$\begingroup$

If you showed that the problem is in P, then you can wait a few hundred years until someone finally proves that P ≠ NP and then it is proven not NP-complete.

Or you can just say "this problem is in P, therefore it is not NP-complete unless P = NP".

Improve this answer
$\endgroup$
-1
$\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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.