# Tag Info

### If everyone believes P ≠ NP, why is everyone sceptical of proof attempts for P ≠ NP?

People are skeptical because: No proof has come from an expert without having been rescinded shortly thereafter So much effort has been put into finding a proof, with no success, that it's assumed ...
• 29.1k
Accepted

### Contradiction proof for inequality of P and NP?

Then it yields that $SAT \in P$ which itself then follows that $SAT \in TIME(n^k)$. Sure. As stands, we are able to do reduce every language in $NP$ to $SAT$. Therefore, $NP \subseteq TIME(n^k)$. ...
• 12.3k
Accepted

### P = NP clarification

Your version of the TSP is actually NP-hard, exactly for the reasons you state. It is hard to check that it is the correct solution. The version of the TSP that is NP-complete is the decision version ...
• 594