# Tag Info

14

The type of argument you are looking for is as follows: If graph isomorphism were NP-complete, then some widely believed complexity assumption fails. There are at least two such arguments: Schöning showed that if graph isomorphism is NP-complete then the polynomial hierarchy collapses to the second level (equivalently, $\Sigma_2^P = \Pi_2^P$). Babai's ...

1

If $X$ is any NP-complete decision problem, then NP consists of all decision problems which are polytime many-one reducible to $X$. We cannot replace polytime many-one reductions with polytime Turing reductions, however (unless NP=coNP), since coSAT is polytime Turing reducible to SAT.

1

I'm assuming that both $A$ and $B$ are decision problems and that we are talking bout Karp reductions. Suppose towards a contradiction that $A \not\in NP$, $A \le_p B$, and $B \in NP$. Then, a non-deterministic polynomial-time Turing machine that decides $A$ would be the following: Use the Karp reduction $f$ from $A$ to $B$ to transform an instance $x$ of $... 1 Recall the (downward) self-reduciblity of a language. A language$L \in \mathrm{NP}$is self-reducible if for every verifer$V$for$L$, there is a polynomial-time Turing machine$M$such that for any oracle$O_{L}$deciding$L$, and any$x \in L$, we have$V(x, M^{O_{L}}(x)) = 1\$. The book gives a proof of the self-reduciblity of SAT. The idea for proving ...

1

The answer by Draconis is wrong in "showing that the new problem is NP-hard." Reducing from something in NP to a new problem does not show NP-hardness. In particular, if a problem A is in P it is also in NP. Suppose there is a reduction from such a polynomial-time solvable A to some new problem B. Then, problem B still can be in P, and in this case ...

Only top voted, non community-wiki answers of a minimum length are eligible