CODEWITHSUNDEEP
algorithmcomplexity-theoryreduction
Idan
Idan

Reputation: 82

Polynomial-time reduction between languages(of problems) in NP and languages(of problems) in P

hello I am having difficulties to understand the topic of P,NP and Polynomial-time reduction. I have tried to search it on web and ask some of my friends , but i havent got any good answer .

I wish to ask a general question about this topic :

let A,B be languages ( or set of problems ) in P let C,D be languages in NP which of the next are Necessarily true ( may be more than 1)

  1. there is a Polynomial-time reduction from A to B
  2. there is a Polynomial-time reduction from A to C
  3. there is a Polynomial-time reduction from C to A
  4. there is a Polynomial-time reduction from C to D

thanks in advance for your answer.

Upvotes: 1

Views: 967

Answers (1)

amit
amit

Reputation: 178441

(1) is true (with the exception of B={} and B={all words}), with the following polynomial reduction:

Let w_t be some word such that B(w_t)=true, and w_f be some word such that B(w_f)=false.
Given a word w: Run A(w). If A(w)=true, return w_t - otherwise, return w_f

The above is polynomial reduction, because all operartions are polynomial and the output of the reduction yields B(f(w))=true if and only if A(w)=true.

(2) is true again, with the same reduction (again, if you can assume there is one w_t and one w_f such as described).

(3) This is wrong, assuming P!=NP.

Assume such a reduction exist, and let it be f:Sigma*->Sigma*.
Examine the problems C=SAT and A is some problem P, and let M_A be a polynomial time algorithm that solves A.

We will show we can solve SAT in polynomial time (but since we assumed P!=NP, it is impossible - contradiction, so f does not exist).

Given an instance of SAT w, run w'=f(w). Run M_A(w'), and answer the same.
The above is clearly polynomial, and it returns always the correct answer - from the definition of polynomial reduction - f(w) is in A if and only if w is in C.
Thus - the above algorithm solves SAT in polynomial time - contradiction.

(4) Is also wrong, since case (3) is covered in it.

Upvotes: 4

Related Questions