## What is NP-Completeness

Expand Messages
• Many people talk about problems being NP-Complete, NP-Hard, etc., but I did not know what these terms exactly were until I took the course Design and Analysis
Message 1 of 5 , Jul 6, 2002
View Source
• 0 Attachment
Many people talk about problems being NP-Complete, NP-Hard, etc., but I
did not know what these terms exactly were until I took the course
"Design and Analysis of Algorithms" this semester. So I'd like to
summarize this subject here.

1. P-Space

P-Space is the set of algorithms that can run in polynomial time (e.g:
O(n), O(n^2), O(n*log(n)), O(n^100), etc). They have some interesting
proprties. Like that a P algorithm will run in polynomial time in every
Turing machine. Or that running one algorithm after another or one using
the other when both are P would make the resultant algorithm P.

2. Reduction

A reduction for algorithm A to algorithm B is another algorithm that can
take the input of A convert it to an input acceptable by B, and then use B
to solve the original input properly. A polynomial reduction is one that
runs at polynomial time.

3. Verification and NP-space

A verification algorithm V for algorithm A is an algorithm that take an
input for A and a possible result, called the witness, and verifies that
the witness is a valid solution to the input.

NP are all the set of all algorithms whose verification runs at polynomial
time. They include all P-space algorithms (because we can verify them by
solving them in Polynomial time).

4. NP-hard

An NP-hard algorithm is an algorithm that there exists a polynomial
reduction from every algorithm in NP to it. An NP-hard algorithm is not
necessarily in NP (it could be harder than that)

5. NP-Complete

An NP-Complete algorithm is an algorithm in NP that is also NP-Hard. I.e:

NPC = Intersection(NP, NPC).

To prove that an algorithm is NP-Complete one needs to:

1. Prove that its verification can be done in Polynomial time.

2. Prove that another NP-Complete algorithm can be reduced to it in
polynomial time.

Of course, it was proven that a certain algorithm (SAT) was NP-Complete
the hard way, by proving any NP algorithm can be reduced to it in
polynomial time.

6. Open Questions
-----------------

It can be shown that NP-Complete algorithms can be solved in exponentail
time (i.e: O(e^P(n))). However, no one has proved that they cannot be
solved in polynomial time, too. If an NP-Complete algorithm can be solved
in Polynomial time than P=NP. If an NP-Complete algorithm can be proven to
require a greater order of growth to solve, than NP is not P.

For some NP-Complete problems, there are approximation algorithms that
can approximate the solution up to a certain order. OTOH, for some such
problems it was proven that finding such an approximation algorithm of any
order, would mean that NP == P.

There is a summary of this subject in Cormen-Leiserson-Rivest and in many
other books.

Regards,

Shlomi Fish

----------------------------------------------------------------------
Shlomi Fish shlomif@...
Home E-mail: shlomif@...

"Let's suppose you have a table with 2^n cups..."
"Wait a second - is n a natural number?"
• ... P-space is normally used as the set of languages for which there are machines that run with polynomial *space* . P is the common name for the class of
Message 2 of 5 , Jul 6, 2002
View Source
• 0 Attachment
On Sat, 6 Jul 2002, Shlomi Fish wrote:

>
> Many people talk about problems being NP-Complete, NP-Hard, etc., but I
> did not know what these terms exactly were until I took the course
> "Design and Analysis of Algorithms" this semester. So I'd like to
> summarize this subject here.
>
> 1. P-Space
>
> P-Space is the set of algorithms that can run in polynomial time (e.g:
> O(n), O(n^2), O(n*log(n)), O(n^100), etc)

P-space is normally used as the set of languages for which there are
machines that run with polynomial *space* . P is the common name for the
class of languages which have polynomial time machines.

(Although nobody has yet proved that P != P-Space)

> . They have some interesting
> proprties. Like that a P algorithm will run in polynomial time in every
> Turing machine. Or that running one algorithm after another or one using
> the other when both are P would make the resultant algorithm P.
>
> 2. Reduction
>
> A reduction for algorithm A to algorithm B is another algorithm that can
> take the input of A convert it to an input acceptable by B, and then use B
> to solve the original input properly. A polynomial reduction is one that
> runs at polynomial time.
>
> 3. Verification and NP-space
>
> A verification algorithm V for algorithm A is an algorithm that take an
> input for A and a possible result, called the witness, and verifies that
> the witness is a valid solution to the input.
>
> NP are all the set of all algorithms whose verification runs at polynomial
> time. They include all P-space algorithms (because we can verify them by
> solving them inPolynomial time).
>
> 4. NP-hard
>
> An NP-hard algorithm is an algorithm that there exists a polynomial
> reduction from every algorithm in NP to it. An NP-hard algorithm is not
> necessarily in NP (it could be harder than that)
>
> 5. NP-Complete
>
> An NP-Complete algorithm is an algorithm in NP that is also NP-Hard. I.e:
>
> NPC = Intersection(NP, NPC).

Intersection(NP, NP-Hard)

>
> To prove that an algorithm is NP-Complete one needs to:
>
> 1. Prove that its verification can be done in Polynomial time.
>
> 2. Prove that another NP-Complete algorithm can be reduced to it in
> polynomial time.
>
> Of course, it was proven that a certain algorithm (SAT) was NP-Complete
> the hard way, by proving any NP algorithm can be reduced to it in
> polynomial time.
>
> 6. Open Questions
> -----------------
>
> It can be shown that NP-Complete algorithms can be solved in exponentail
> time (i.e: O(e^P(n))). However, no one has proved that they cannot be
> solved in polynomial time, too. If an NP-Complete algorithm can be solved
> in Polynomial time than P=NP.If an NP-Complete algorithm can be proven to
> require a greater order of growth to solve, than NP is not P.
>
> For some NP-Complete problems, there are approximation algorithms that
> can approximate the solution up to a certain order. OTOH, for some such
> problems it was proven that finding such an approximation algorithm of any
> order, would mean that NP == P.
>
> There is a summary of this subject in Cormen-Leiserson-Rivest and in many
> other books.

--
Tzafrir Cohen
mailto:tzafrir@...
http://www.technion.ac.il/~tzafrir
• ... Do you have an example for a problem that is NP-Hard, but not NP? I don t think I ever saw one. Thanks, Chen.
Message 3 of 5 , Jul 6, 2002
View Source
• 0 Attachment
> 4. NP-hard
>
> An NP-hard algorithm is an algorithm that there exists a polynomial
> reduction from every algorithm in NP to it. An NP-hard
> algorithm is not
> necessarily in NP (it could be harder than that)

Do you have an example for a problem that is NP-Hard, but not NP?
I don't think I ever saw one.

Thanks,
Chen.
• ... If a certain language is NP-hard, it means that any NP language can be reduced to it (a misleading verb!): if you can solve it in polynomial time, you can
Message 4 of 5 , Jul 6, 2002
View Source
• 0 Attachment
On Sat, 6 Jul 2002, Chen Shapira wrote:

>
> > 4. NP-hard
> >
> > An NP-hard algorithm is an algorithm that there exists a polynomial
> > reduction from every algorithm in NP to it. An NP-hard
> > algorithm is not necessarily in NP (it could be harder than that)
>
> Do you have an example for a problem that is NP-Hard, but not NP?
> I don't think I ever saw one.

If a certain language is NP-hard, it means that any NP language can be
reduced to it (a misleading verb!): if you can solve it in polynomial
time, you can solve any NP language in polynomial time.

Here is a semi-formal proof that the halting problem is NP-Hard:

Proof
"""""
Suppose, for instance, that you happened to have an oracle for the halting
problem. That is: your machine is equiped with an extra helper procedure
to which you give a turing machine and input, and it answers if the
machine will halt on the input.

So if you want to have a machine that can solve any NP language, that is:
given any NP language, L, you know that there is a [polynomial] machine Mp
that accepts the verification relation of L.

So you simply build a machine that tries to run Mp on any possible
"witness", until it finds such a witness. Then it asks the oracle (for the
halting problem) if this machine will stop.

All of your operations could be easily done in polynomial time: you know
in advance what Mp is. So all you have to do is to create a machine that
runs Mp in a loop.

If a witness exists, the created machine would eventually find it, if run.
Therefore it would stop. The oracle will therefore answer that it it would

If there is no witness, the machine would keep looking for it, and never
stop. Therefore the oracle will answer that it wouldn't stop.

>>>>>>>>>>>>>>>>>>>> End proof

So what did we learn?

1. It is dangerous to have Machines with HP oracles. You can never know
what they will do ;-)

2. The verb "reduce" is confusing . the empty language is easily reducable
(with any reasonable reduction method) to almost any other language.

3. So there are enough languages that are not even verfiable in polynomial
time, but if you could ignore their running time and resources, you
would have solved any NP problem easily.

--
Tzafrir Cohen
mailto:tzafrir@...
http://www.technion.ac.il/~tzafrir
• ... Actually, Tzafrir, what you describe is normally spelled PSPACE , with capital letters. But you re right that using the phrase P space to refer to the
Message 5 of 5 , Jul 6, 2002
View Source
• 0 Attachment
On Sat, Jul 06, 2002, Tzafrir Cohen wrote about "Re: [hackers-il] What is NP-Completeness":
> On Sat, 6 Jul 2002, Shlomi Fish wrote:
> > 1. P-Space
> >
> > P-Space is the set of algorithms that can run in polynomial time (e.g:
> > O(n), O(n^2), O(n*log(n)), O(n^100), etc)
>
> P-space is normally used as the set of languages for which there are
> machines that run with polynomial *space* . P is the common name for the
> class of languages which have polynomial time machines.

Actually, Tzafrir, what you describe is normally spelled "PSPACE", with
capital letters. But you're right that using the phrase "P space" to refer
to the complexity class "P" is indeed ambiguous, to say the least, to
people who also know about "PSPACE".

Anyway, Shlomi's summary was mostly correct, and good, but I doubt that a
person without previous knowledge of these issues would be able to grasp the
difference between "algorithm" and "verification" (of what, by the way?
where is your "proof" that you need to verify?), or the concept of languages,
and Turing machines (and non-deterministic Turing machines, the reason NP,
non-deterministic polynomial, got its name), from such a short introduction.
Anyone who's interested in more "meat" about these issues, should probably
take the course "Computation Theory" and later "Complexity Theory" in the
Technion, or some comparable course in another university. Or just read