Time Complexity and Polynomial Reduction

72 Views Asked by At

Let $A$ be an NP- complete problem, if there is an algorithm that solve $A$ in $2^{o(n)}$, does this means that $NP \not= ExpTime$ ? if this is true then i have a follow up question.

Let $A,B$ be 2 NP Complete problems, pick 2 of your favourites like 3-Coloring and Clique problem assume that we can solve $A$ in $2^{\sqrt{n}}$ and $B$ is reduced to $A$ from $n$ nodes in $B$ to $n^2$ nodes in $A$ so to solve $B$ problem with $n$ nodes we first reduce it to $A$ problem with $n^2$ nodes and solve it in $2^{\sqrt{n^2}} = 2^n$ in exponential time !!!! (what just happened here), where is my reasoning false ?!

1

There are 1 best solutions below

0
On BEST ANSWER

Let $A$ be an NP- complete problem, if there is an algorithm that solve $A$ in $2^{o(n)}$, does this means that $NP \not= ExpTime$ ?

No, it would not. It is known that $NP\subseteq ExpTime$ (with $PSpace$ in-between), and the only way to have non-equality would be if there were a problem in $ExpTime$ that is not in $NP$. That is not what you have demonstrated here.

A problem being $NP$-complete means "if this problem has a polynomial solution, then every other $NP$ problem has a polynomial solution by reducing to this problem". As you have discovered, that does not imply "if this problem has a sub-exponential solution, then all $NP$ problems have a sub-exponential solution by reducing to this problem".