# 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.9k
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)$. ...
• 13.8k
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 ...
• 604

• 4,372

### Does a polynomial solution for an NP-complete problem that can only be implemented for small N *still* imply P=NP?

Time complexity "for small inputs" simply doesn't make sense, because the definition of time complexity is based on the limit of the running time as the input size grows to infinity.
• 1,177
Accepted

### What is the utility of proving P=NP if we can't find an algorithm that can solve any NP problem in polynomial time?

In short, if we prove $P=NP$, then we know a whole lot more about computation than we did before, even if we don't find the algorithm, and that was the objective behind research on $P=NP$ all along. ...
• 4,372
### Why does this not prove $P\neq NP$?
What Fiorini et al. show is the following: The TSP polytope $P_n$ over $n$ points is a polytope in $\binom{n}{2}$ dimensions whose vertices correspond to all Hamiltonian cycles in $K_n$ (the complete ...