How to prove that a problem is NP complete

Question

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

User · Answer

In order to prove that a problem L is NP-complete  we need to do the following steps    Prove your problem L belongs to NP  that is that given a solution you can verify it in polynomial time   Select a known NP-complete problem L  Describe an algorithm f that transforms L  into L Prove that your algorithm is correct  formally  x   L  if and only if f x    L   Prove that algo f runs in polynomial time

User · Answer

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.

User · Answer

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  quot any possible subset of vertices in graph G of size k quot   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  quot possible subset of vertices in G of size k quot  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 - gt  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   gt  Y in your problem  and Y in your problem   gt  X in SAT    marcog s answer has a link with several other NP-complete problems you could reduce to your problem  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

User · Answer

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

User · Answer

Get familiar to a subset of NP Complete problems 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  Prove that your problem is in NP   design an algorithm which can verify in polynomial time whether an instance is a solution

[algorithm] How to prove that a problem is NP complete?

The answer is

Examples related to algorithm

Tags