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