Subject: What is NP-Completeness

From: Shlomi Fish <[email-masked]>
Date: Sat, 6 Jul 2002 15:56:58 +0300 (IDT)

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        [email-masked]
Home Page:         http://t2.technion.ac.il/~shlomif/
Home E-mail:       [email-masked]

"Let's suppose you have a table with 2^n cups..."
"Wait a second - is n a natural number?"

---

From: Tzafrir Cohen <[email-masked]>
Date: Sat, 6 Jul 2002 19:36:24 +0300 (IDT)

On Sat, 6 Jul 2002, Shlomi Fish wrote:

> 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
> solving them inPolynomial time).
>
> 4. NP-hard
>

Intersection(NP, NP-Hard)

> in Polynomial time than P=NP.If an NP-Complete algorithm can be proven to

-- 
Tzafrir Cohen
mailto:[email-masked]
http://www.technion.ac.il/~tzafrir

---

From: "Nadav Har'El" <[email-masked]>
Date: Sun, 7 Jul 2002 01:40:50 +0300

> 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
a book that talks about this subject, if you have access to a good CS
library.

Good night :) (I should be sleeping in such hours...)

-- 
Nadav Har'El                        |       Sunday, Jul 7 2002, 27 Tammuz 5762
[email-masked]             |-----------------------------------------
Phone: +972-53-245868, ICQ 13349191 |A Life? Cool! Where can I download one of
http://nadav.harel.org.il           |those from?