How to prove a problem is NOT NP-Complete?

Problem Detail: 

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.

Asked By : Untitled

Answered By : Pål GD

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/12812