recategorized by
2,067 views
7 votes
7 votes

Suppose we have constructed a polynomial time reduction from problem $A$ to problem $B$. Which of the following can we infer from this fact?

  1. If the best algorithm for $B$ takes exponential time, there is no polynomial time algorithm for $A$.
  2. If the best algorithm for $A$ takes exponential time, there is no polynomial time algorithm for $B$.
  3. If we have a polynomial time algorithm for $A$, we must also have a polynomial time algorithm for $B$.
  4. If we don’t know whether there is a polynomial time algorithm for $B$, there cannot be a polynomial time algorithm for $A$.
recategorized by

3 Answers

Best answer
11 votes
11 votes

1. A <p B, B takes exponential time. It means A is not more harder than B, So A won't take more time than the exponential. this reduction tells the upper bound, but we can't comment anything on lower bound, in fact A may be solved in O(1) time.
2.  A <p B, the best algorithm for A takes exponential time, there is no polynomial time algorithm for B.
yes, this is correct, because if B can be solved in polynomial time, then we can reduce problem A into problem B, and then A can be solved in polynomial time too. But as mentioned, Best algorithm for A takes exponential time.

3. A <p B,
If we have a polynomial time algorithm for A, we must also have a polynomial time algorithm for B.
This is not correct, B even may take exponential time. It only tells that B can not be easier than A, Because if B is easier than A, then We can reduce A to B and can solve A in less than polynomial time.

4. A <p B,
     If we don’t know whether there is a polynomial time algorithm for B, there can not be a polynomial time algorithm for A.
This is also false, because if B has polynomial time algorithm then A also has polynomial time algorithm, because we can reduce A to B, and can solve A in polynomial time.
If B doesn't have polynomial time algorithm, then still A can have polynomial time algorithm, because in this case A is not easier than B.

Correct Answer: $B$

edited by
9 votes
9 votes

Problem $A$ reduces to Problem $B$,

Option (B) If the best algorithm for A takes exponential time, there is no polynomial time algorithm for B. will be correct. 

edited by
Answer:

Related questions

13 votes
13 votes
5 answers
1
go_editor asked May 27, 2016
5,503 views
How many times is the comparison $i \geq n$ performed in the following program?int i=85, n=5; main() { while (i >= n) { i=i-1; n=n+1; } }$40$$41$$42$$43$
4 votes
4 votes
2 answers
3