96
votes
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.7k
57
votes
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.7k
47
votes
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
44
votes
If everyone believes P ≠ NP, why is everyone sceptical of proof attempts for P ≠ NP?
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 \...
- 9,425
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-...
- 81.4k
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 ...
- 81.4k
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, ...
- 275k
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. ...
- 824
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 ...
- 29.7k
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 ...
D.W.♦
- 156k
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 ...
- 4,979
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 ...
- 419
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 ...
D.W.♦
- 156k
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, ...
- 81.4k
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 ...
- 471
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 ...
- 887
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 ...
- 233
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 ...
- 7,768
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 ...
- 11k
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:...
- 2,713
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 ...
- 81.4k
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,...
- 275k
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 ...
D.W.♦
- 156k
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 ...
- 11.5k
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, ...
- 824
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 ...
- 531
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 ...
- 22.2k
8
votes
Would proving P≠NP be harder than proving P=NP?
Well you basically have the idea. We generally think that P != NP but have no idea how we would even prove these things are not equal.
Conversely, if P = NP, you'd think we would have found an ...
- 497
8
votes
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,167
Only top scored, non community-wiki answers of a minimum length are eligible