Search code examples
algorithmcomplexity-theoryreduction

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.

Solution

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