- 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 Page: http://t2.technion.ac.il/~shlomif/

Home E-mail: shlomif@...

"Let's suppose you have a table with 2^n cups..."

"Wait a second - is n a natural number?" - On Sat, 6 Jul 2002, Shlomi Fish wrote:

>

P-space is normally used as the set of languages for which there are

> 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)

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

Intersection(NP, NP-Hard)

> 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).

>

--

> 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 > 4. NP-hard

Do you have an example for a problem that is NP-Hard, but not NP?

>

> 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)

I don't think I ever saw one.

Thanks,

Chen.- On Sat, 6 Jul 2002, Chen Shapira wrote:

>

If a certain language is NP-hard, it means that any NP language can be

> > 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.

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:

(Feel free to skip to its end)

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

stop, and your machine will answer yes.

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 - On Sat, Jul 06, 2002, Tzafrir Cohen wrote about "Re: [hackers-il] What is NP-Completeness":
> On Sat, 6 Jul 2002, Shlomi Fish wrote:

Actually, Tzafrir, what you describe is normally spelled "PSPACE", with

> > 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.

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

nyh@... |-----------------------------------------

Phone: +972-53-245868, ICQ 13349191 |A Life? Cool! Where can I download one of

http://nadav.harel.org.il |those from?