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 ...
Joey Eremondi's user avatar
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)$. ...
orlp's user avatar
  • 13.4k
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 ...
D.R's user avatar
  • 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 \...
Evil's user avatar
  • 9,455
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 ...
David Richerby's user avatar
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. ...
Yakk's user avatar
  • 824
24 votes
Accepted

Are there languages L1 ⊆ L2 ⊆ L3 when L1 and L3 are NP-Complete languages and L2 ∈ P?

Consider the following problems: $L_1$: Input: two graphs $G_1$ and $G_2$ Question: does $G_1$ contain an hamiltonian path and is $G_2$ complete? $L_2$: Input: two graphs $G_1$ and $G_2$ Question: ...
Nathaniel's user avatar
  • 15.6k
23 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 ...
dkaeae's user avatar
  • 5,017
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 ...
Joey Eremondi's user avatar
20 votes

Are there languages L1 ⊆ L2 ⊆ L3 when L1 and L3 are NP-Complete languages and L2 ∈ P?

That’s trivial. Take an NP-complete language $L$ with three symbols $a, b$, and $c$. Let $L’$ be the same language with $a, b, c$ replaced with $d, e, f$. Now pick $L_1 = L, L_2 = (a \cup b \cup c)^*$,...
gnasher729's user avatar
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 ...
Ryoji's user avatar
  • 419
18 votes

Are there languages L1 ⊆ L2 ⊆ L3 when L1 and L3 are NP-Complete languages and L2 ∈ P?

The existing answers provide good examples of the requested condition, but I think there's some intuition missing. What makes a language hard to decide is not what it contains, but the combination of ...
Scott McPeak's user avatar
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.'s user avatar
  • 159k
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 ...
NaturalLogZ's user avatar
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 ...
Ivan Smirnov's user avatar
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 ...
Discrete lizard's user avatar
  • 8,248
12 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:...
Noah Schweber's user avatar
11 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 ...
David Richerby's user avatar
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,...
Yuval Filmus's user avatar
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.'s user avatar
  • 159k
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 ...
nir shahar's user avatar
  • 11.6k
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 ...
Thomas C. G. de Vilhena's user avatar
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 ...
Mario Carneiro's user avatar
9 votes

Are there languages L1 ⊆ L2 ⊆ L3 when L1 and L3 are NP-Complete languages and L2 ∈ P?

The constructions in the other answers are nice, but end up with somewhat artificial languages created by disjunction. There are more natural languages that also do the trick: Let $L_1$ be the set of ...
Discrete lizard's user avatar
  • 8,248
8 votes

Why can't we exploite finiteness to prove incompleteness in NP?

Here is a good reason why finiteness does not help: Let $P_{inf}$ and $NP_{inf}$ be the sets of infinite languages in $P$ and $NP$. Then we may focus on proving $P_{inf}\not=NP_{inf}$, rather than $P\...
Lieuwe Vinkhuijzen's user avatar
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.
user541686's user avatar
  • 1,167
8 votes
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. ...
Lieuwe Vinkhuijzen's user avatar
8 votes
Accepted

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 ...
Yuval Filmus's user avatar
8 votes
Accepted

Why doesn't descriptive complexity theory solve P = NP?

Note the difference between second-order logic, and existential second order logic. Full logic is much more powerful than existential logic. Also, it's important not to underestimate the power of a ...
Joey Eremondi's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible