Subject: RE: [hackers-il] What is NP-Completeness

From: Chen Shapira <[email-masked]>
Date: Sat, 6 Jul 2002 18:41:51 +0200

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

---

From: Tzafrir Cohen <[email-masked]>
Date: Sat, 6 Jul 2002 20:10:29 +0300 (IDT)

On Sat, 6 Jul 2002, Chen Shapira wrote:

> > algorithm is not necessarily in NP (it could be harder than that)
>

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:

(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:[email-masked]
http://www.technion.ac.il/~tzafrir