# 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 ...
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)$. ...
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 ...

Beliefs are orthogonal to proofs. Belief may direct attempted solutions by researchers or rather their main interest but this does not prevent them from checking a proof anyway. The problem with $P \... 30 votes Accepted ### How to prove P$\neq$NP? There are three main ways I'm aware of that could prove that P$\,\neq\,$NP. Showing that there is some problem that is in NP but not in P. You're probably familiar with the proof that comparison-... 29 votes ### Does a polynomial solution for an NP-complete problem that can only be implemented for small N *still* imply P=NP? If you mean that the polynomial-time algorithm only works for inputs up to some fixed size, it shows nothing at all. Any problem at all (even if it's undecidable, let alone NP-complete) becomes a ... 26 votes Accepted ### Would proving P≠NP be harder than proving P=NP? As Raphael explains, this question is ill-posed, since at most one of P=NP and P≠NP should be provable at all. However, a similar question arises in theoretical computer science in several guises, ... 24 votes ### If everyone believes P ≠ NP, why is everyone sceptical of proof attempts for P ≠ NP? A few reasons, some generic and some specific. The generic reason is that this is a long-known famous problem which many smart people have tried to solve, and many smart people have gotten wrong. ... 23 votes Accepted ### How hard would it be to state P vs. NP in a proof assistant? I'm going to disagree with DW. I think that it is possible (although difficult) for a P vs. NP result to be stated in a proof assistant, and moreover, I wouldn't trust any supposed proofs unless they ... 22 votes Accepted ### Evolving artificial neural networks for solving NP problems No. This direction is unlikely to be useful, for two reasons: Most computer scientists believe that P$\ne$NP. Assuming P$\ne$NP, this means there does not exist any polynomial-time algorithm to ... 22 votes Accepted ### If graph isomorphism is in P, is then P = NP? We don't know. We do know that$\textbf{P} = \textbf{NP}$implies graph isomorphism is in$\textbf{P}$, but the other implication has not been proven (to the best of my knowledge). It is suspected ... 19 votes ### If a problem is in P solved via dynamic programming, is it also in NP? Any problem in P is also in NP A decision problem that's in P is also in NP, because you can give the verification logic like this: for yes instance x, use empty ... 17 votes Accepted ### Is detecting easy instances of NP-hard problems easy? The problem isn't really well-posed. For any particular instance, there is a single solution, say$S$. Consequently, we can imagine an algorithm that has the answer$S$hardcoded in: no matter what ... 15 votes ### If$\mathbf{P} = \mathbf{NP}$, then is$\mathbf{L} = \mathbf{NL}$? This is an open research question. At our current state of knowledge, knowing$\mathbf{P}=\mathbf{NP}$would neither imply$\mathbf{L}=\mathbf{NL}$nor$\mathbf{L}\neq\mathbf{NL}$. And, conversely, ... 15 votes ### P = NP clarification There is a lot of decent answers here but none clear up a couple fairly important misunderstandings you seem to have. Both P and NP are classes of what are called "decision problems." These are ... 13 votes Accepted ### Why the need for TSP solvers when there are SAT solvers? TL;DR: polynomial reduction increases the size of a problem; using a specific solver allows you to exploit the structure of a problem. When you reduce one NP-complete problem to another one, the size ... 12 votes ### What is the definition of P, NP, NP-complete and NP-hard? From the P vs. NP and the Computational Complexity Zoo video. For a computer with a really big version of a problem... P problems easy to solve (rubix cube) NP problems hard to solve - but ... 12 votes Accepted ### Naive argument that P ≠ NP The error in your argument is the claim Nothing is known a priori about the function$f$, (...) so it is necessary to plug in all$2^n$values. , which is simply false. I will demonstrate why it ... 11 votes ### Evolving artificial neural networks for solving NP problems It seems other answers while informative/ helpful are not actually understanding your question exactly and are reading a little too much into it. You didn't ask if neural networks would outperform ... 11 votes ### A problem in NP but not NP-complete? As written, the question is a bit trivial: if NP = NP-complete, then since P$\subseteq$NP we get P=NP since every problem in P would be NP-complete. I suspect what's meant, though, is the following:... 10 votes ### What is wrong with this conditional proof of P=NP? Suppose L=P. Let A be a problem in NP. By the verifier definition of NP, each positive solution to A has a witness that can be verified in polynomial time. Since P=L, the same solution can be verified ... 10 votes ### P=NP, isn't it? Every CNF is falsifiable (choose a clause and choose a truth assignment which falsifies it). Unfortunately, the opposite of "CNF$\varphi$is satisfiable" is not "CNF$\varphi$is falsifiable". Rather,... 10 votes ### How hard would it be to state P vs. NP in a proof assistant? Using proof assistants for this purpose is certainly possible in principle, but I suspect it would take more effort than most folks who write such proofs would be interested in putting in. It would ... 10 votes ### Is there any NP-hard problem which was proven to be solved in polynomial time or at least close to polynomial time? By definition, if you were to find a polynomial time algorithm for an NP-hard (or NP-complete) problem, then$P=NP$. So, short answer is - no. However, its possible to think instead of solving the ... 9 votes ### Would proving P≠NP be harder than proving P=NP? We have not ruled out the possibility of a simple proof that P=NP. If someone tomorrow comes up with an algorithm that solves a NP-complete problem in P time, the world changes. On the other hand, ... 9 votes ### What is the definition of P, NP, NP-complete and NP-hard? P, NP, NP-complete and NP-hard are complexity classes, classifying problems according to the algorithmic complexity for solving them. In short, they're based on three properties: Solvable in ... 9 votes ### How hard would it be to state P vs. NP in a proof assistant? I can give a direct answer to (2):$P\ne NP$has been stated in Lean (along with the other main results of Cook's paper, where the conjecture was first described), as part of the Formal Abstracts ... 8 votes ### What would be the real-world implications of a constructive$P=NP\$ proof?

P vs. NP, technically vs. morally As Yuval said it is possible that P=NP is technically true but morally false. P=NP is morally true (even if not necessarily technically) if there is a fast ...