Thursday, July 21, 2005

If NP = P, then any problem not empty and not Σ* will be NP-complete

The answer was greatly supported by Prof. G. S. Huang.


------------------------------------------------------------------------------------------------

You are wrong.
Since in the assumption one supposes that P=NP, any problem in NP is also in P. Therefore you can solve any NP problem in polynomial time by a deterministic Turing machine under this assumption.

Your another point criticizes on how to find a "yes" instance and a "no" instance from A (which is the one that we intend to show NP-complete). This is indeed not a problem since such two instances always exists and do not bother one really to find them. Actually, you don't have to spend any time to find them since you only have to show that such a reduction does "EXIST" as long as such twoinstances exist.

----- Original Message -----
From: Chuang-Chieh Lin
To: Professor G. S. Huang
Sent: Thursday, July 14, 2005 3:23 PM
Subject: Re: Communication

Dear Professor Huang:

Thank you for your advise.
Recently I found some answers similar to yours.

http://www.cs.brown.edu/courses/cs152/hw5_sol-99.ps
http://www.cc.gatech.edu/classes/AY2005/cs4510_spring/hw4sol.pdf

However, I am still puzzled at how do we find "Y" and "N" in polynomial time.
Shouldn't we require a Turing machine doing this work?
It seems that finding a "Y" and finding an "N" would require exponential time
in the worst case although deciding whether an instance is an "Y" or "N" is of
polynomial time.

Sincerely yours,
Chuang-Chieh Lin

As for your problem, I think the reduction in Sipser's book
is the polynomial reduction. Suppose A is in P and B is in NP.
All you have to do is to prove that any B can be reduced to
such A in polynomial time.

There exist "yes" instances and "no" instances of A since A is not empty or full.
Let's call Y a "yes" instance and N a "no" instance. The reduction is as follows. For any instance of B, we do

1. Solve the instance in polynomial time. This becomes possible since we assume NP=P.
2. If the answer is yes, output Y; else output N.

This is indeed a polynomail-time reduction and you can show
that the instance is "yes" IF AND ONLY IF the output is a
"yes" instance of A, though this reduction is a little nonsense.
Therefore one can claim that A is NP-complete since A is in NP.


A letter coming from Professor G. S. Huang.
-----------------------------------------------------

1 comment:

Joseph, Chuang-Chieh Lin said...

I am very grateful to Prof. Huang for his advise.

Really.