Decision Problems and Poly Time

79 Views Asked by At

We have Two Decision Problem A and B. we know A is NP-Complete, but B can be solved in $O(n^2lg^4n)$, and we know $B \leq_pA $ (i.e each problem of B can be convert to a problem of A in Polynomial Time). Which of them is inferred from the above axioms.

1- P= NP and each NP problem can be solved in $O(n^3)$

2- P=NP and some NP Problems need times more than $O(n^3)$ to solve.

3-$ P \neq NP$

40 none of them.

this is a question on Entrance Exam on Computer Science on 2013. one of my friends says second is true and the first is false.

EDIT: I mentioned the whole question.

1

There are 1 best solutions below

9
On BEST ANSWER

If $B\le A$, there is no good answer, because it's an open question to know if $P=NP$, so we don't know if one of them or none of them can be inferred from the hypotheses. Note that $B\le A$ is suspicious because it can be inferred from the fact that $A$ is $NP$-complete, so it is not really an hypothesis.

if $A\le B$, it means that we can solve $A$ in polynomial time. As $A$ is $NP$-complete, it means that $NP\subseteq P$ so $P=NP$. However it is easy, by diagonalization, to create problems in $P$ that can be solved in more than $O(n^3)$. So the second answer is good in this case.