125

I have problem with scheduling. I need to prove that the problem is NP complete. What can be the methods to prove it NP complete?

Improve this question
1
  • Read "Reducibility Among Combinatorial Problems" by Karp. Commented Jan 19, 2014 at 10:59

5 Answers 5

Reset to default
158

To show a problem is NP-complete, you need to:

Show it is in NP

In other words, given some information C, you can create a polynomial time algorithm V that will verify for every possible input X whether X is in your domain or not.

Example

Prove that the problem of vertex covers (that is, for some graph G, does it have a vertex cover set of size k such that every edge in G has at least one vertex in the cover set?) is in NP:

  • our input X is some graph G and some number k (this is from the problem definition)

  • Take our information C to be "any possible subset of vertices in graph G of size k"

  • Then we can write an algorithm V that, given G, k and C, will return whether that set of vertices is a vertex cover for G or not, in polynomial time.

Then for every graph G, if there exists some "possible subset of vertices in G of size k" which is a vertex cover, then G is in NP.

Note that we do not need to find C in polynomial time. If we could, the problem would be in `P.

Note that algorithm V should work for every G, for some C. For every input, there should exist information that could help us verify whether the input is in the problem domain or not. That is, there should not be an input where the information doesn't exist.

Prove it is NP-Hard

This involves getting a known NP-complete problem like SAT, the set of boolean expressions in the form:

(A or B or C) and (D or E or F) and ...

where the expression is satisfiable, that is there exists some setting for these booleans, which makes the expression true.

Then reduce the NP-complete problem to your problem in polynomial time.

That is, given some input X for SAT (or whatever NP-complete problem you are using), create some input Y for your problem, such that X is in SAT if and only if Y is in your problem. The function f : X -> Y must run in polynomial time.

In the example above, the input Y would be the graph G and the size of the vertex cover k.

For a full proof, you'd have to prove both:

  • that X is in SAT => Y in your problem

  • and Y in your problem => X in SAT.

Wikipedia has a good list of several NP-complete problems you could reduce to your problem, see here:

https://en.wikipedia.org/wiki/List_of_NP-complete_problems

Footnote: In step 2 (Prove it is NP-hard), reducing another NP-hard (not necessarily NP-complete) problem to the current problem will do, since NP-complete problems are a subset of NP-hard problems (that are also in NP).

Improve this answer
Sign up to request clarification or add additional context in comments.

8 Comments

I wonder if there is missing data or a circular reasoning behind this. I mean how to 'prove' a problem is in NP without referring it to other problem that 'is already in NP'? It's like say "it's made of iron because its part are known to be iron", that's not an iron proof.
As far as I remember, there is a theorem called the Cook-Levin theorem which states that SAT is NP-complete. That proof is quite a bit more complicated than what I outlined above and I don't think I can explain it in my own words.
To be more precise, the Cook-Levin Theorem states that SAT is NP-complete: any problem in NP can be reduced in polynomial time by a deterministic Turing machine to the problem of determining whether a Boolean formula is satisfiable (SAT). So that's the missing piece you were asking about. If you look up the theorem on Wikipedia there is a proof, and you can reference the theorem in your proof. That said, reducing SAT to a given problem is the way I was taught to prove NP-completeness.
So my question ends up being if SAT could be solved in polynomial i.e. the P = NP problem.. Thanks for your answer.
@MichaelM I've modified the answer to include a link to wikipedia's list of NP-complete problems, which seems like a good place to start looking for something to reduce. I think the link I was previously referencing was either edited itself or the page it was linking to was edited.
|
25

You need to reduce an NP-Complete problem to the problem you have. If the reduction can be done in polynomial time then you have proven that your problem is NP-complete, if the problem is already in NP, because:

It is not easier than the NP-complete problem, since it can be reduced to it in polynomial time which makes the problem NP-Hard.

See the end of http://www.ics.uci.edu/~eppstein/161/960312.html for more.

Improve this answer

3 Comments

+1 someone who explains understandably. instead of saying a bunch of references to keywords I hardly understand.
The first sentence is back-to-front: you need to reduce the known NP-complete problem to your own problem. This shows that your problem is at least as hard as the known NP-complete problem. Part (b) is also incorrect: if you have found the reduction then you already know that your problem is NP-hard; the only question is whether it is in NP at all (some problems, like the Halting Problem, are not). Iff it is NP-hard and in NP, then it is NP-complete (i.e. "NP-complete" is more specific than "NP-hard").
I wouldn't say a) leads to a contradiction, since we don't know that P != NP.
19

In order to prove that a problem L is NP-complete, we need to do the following steps:

  1. Prove your problem L belongs to NP (that is that given a solution you can verify it in polynomial time)
  2. Select a known NP-complete problem L'
  3. Describe an algorithm f that transforms L' into L
  4. Prove that your algorithm is correct (formally: x ∈ L' if and only if f(x) ∈ L )
  5. Prove that algo f runs in polynomial time
Improve this answer

Comments

8

First, you show that it lies in NP at all.

Then you find another problem that you already know is NP complete and show how you polynomially reduce NP Hard problem to your problem.

Improve this answer

1 Comment

No. You need to show that you can reduce from an NP complete problem to your NP problem to prove NP completeness AND prove it is in NP at all. NP hard doesn't come into this, unless you can't prove its in NP.
7
  1. Get familiar to a subset of NP Complete problems
  2. Prove NP Hardness : Reduce an arbitrary instance of an NP complete problem to an instance of your problem. This is the biggest piece of a pie and where the familiarity with NP Complete problems pays. The reduction will be more or less difficult depending on the NP Complete problem you choose.
  3. Prove that your problem is in NP : design an algorithm which can verify in polynomial time whether an instance is a solution.
Improve this answer

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.