Hot answers tagged

428

I think the Wikipedia articles $\mathsf{P}$, $\mathsf{NP}$, and $\mathsf{P}$ vs. $\mathsf{NP}$ are quite good. Still here is what I would say: Part I, Part II [I will use remarks inside brackets to discuss some technical details which you can skip if you want.] Part I Decision Problems There are various kinds of computational problems. However in an ...


212

Part II Continued from Part I. The previous one exceeded the maximum number of letters allowed in an answer (30000) so I am breaking it in two. $\mathsf{NP}$-completeness: Universal $\mathsf{NP}$ Problems OK, so far we have discussed the class of efficiently solvable problems ($\mathsf{P}$) and the class of efficiently verifiable problems ($\mathsf{NP}$). As ...


95

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 one will be either substantially complicated, or invent new mathematics for the proof The "proofs" that arise frequently fail to address hurdles which are known ...


56

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)$. No. Polynomial time reductions aren't free. We can say it takes $O(n^{r(L)})$ time to reduce language $L$ to $SAT$, where $r(L)$ is the exponent in the ...


46

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 of the problem (quoting Wikipedia): The decision version of the TSP (where given a length L, the task is to decide whether the graph has a tour of at most L) ...


44

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 \ne NP$ that many standard ways of attempting a proof are already excluded as not sufficient to infer anything, see here for further details. There is no ...


35

People have given good answers assuming that $P=NP$ with some really large constant. I'm going to play the optimist and assume that we find a proof of $P=NP$ with a tractably small constant. Perhaps not likely, but I'm going to try to give some insight into what sorts of things would happen if we could efficiently solve all $NP$ problems. Compilers: Some ...


32

We won't necessarily see any effects. Suppose that somebody finds an algorithm that solves 3SAT on $n$ variables in $2^{100} n$ basic operations. You won't be able to run this algorithm on any instance, since it takes too long. Or suppose that she finds an algorithm running in $n^{100}$ basic operations. We will only be able to use it on 3SAT instances on a ...


29

More than useful mentioned answers, I recommend you highly to watch "Beyond Computation: The P vs NP Problem" by Michael Sipser. I think this video should be archived as one of the leading teaching video in computer science.! Enjoy!


29

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 finite language when restricted to instances of constant size. All finite languages can be decided in constant time. If you mean that the polynomial-time algorithm ...


28

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-based sorting need time $\Omega(n\log n)$ to sort a list of $n$ items. One could, in principle, produce a similar proof showing that 3SAT or some other NP-complete ...


26

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, the most conspicuous of which is in the field of approximation algorithms. Given an NP-hard optimization problem (say, maximization), we can ask how well we ...


23

No. It is another open problem and certainly related, but different. The complexity class co-$\mathsf{NP}$ is the set of languages whose complements are in $\mathsf{NP}$; that is, the set of decision problems for which a "no" answer has a deterministic polynomial-time verifier. So for example, the question "Is this SAT formula unsatisfiable?" If the answer ...


23

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. The odds that any one new proof is valid is extremely low based off this history. In this specific case, there has been research on what proofs don't work. It ...


23

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 were formalized in this way, unless they came from very reputable sources. In particular, none of the resources DW states are based on type theory, which is a ...


22

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 solve any NP-complete problem. If you want your neural network to solve the problem in a reasonable amount of time, then it can't be too large, and thus the ...


22

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 graph isomorphism is $\textbf{NP}$-intermediate (i.e., it is in $\textbf{NP} \setminus \textbf{P}$ and not $\textbf{NP}$-complete). This question as well as this ...


19

It is maybe easier to consider the contrapositive, that is ${\sf P}={\sf NP} \Rightarrow {\sf NP}={\sf coNP}$. So assume ${\sf P}={\sf NP}$, then for every $L\in {\sf NP}$, we have $L\in {\sf P}$, and since the languages in ${\sf P}$ are closed under complement, $\bar L\in {\sf P}$ and therefore $L\in {\sf coNP}$. for every $L\in {\sf coNP}$, we have $\...


19

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 string as a certificate, and solve x in polynomial time. You get the result that it's yes instance (that's by definition of P) and that means verification is done in polynomial time. Note that, ...


17

There are two possible bugs in this proof: When you say "decider" - you mean a deterministic TM. In this case, the best translation (to our knowledge) from an NP machine to a deterministic machine may yield a machine that runs in exponential time, so after complementing you will have a decider for the complement in exponential time, proving that $co-NP\...


17

A very nice read here is [1], where Impagliazzo considers five possible "worlds" where relationships between complexity classes are different. For instance, in a world called Algorithmica (see Section 2.1), we have that $\sf P = NP$ (or some other "moral equivalent" holds, such as $\sf NP \subseteq BPP$). In Algorithmica, virtually any optimization problem ...


17

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 input you give it, all it does is just print $S$. This answer counts as a deterministic polynomial-time algorithm that solves this particular instance $I$. ...


16

Here's another way of looking at the point that Shaull makes with respect to "deciders". A problem is in NP if and only if there is an algorithm $V: \{0,1\}^n \times \{0,1\}^{\mathrm{poly}(n)} \to \{0,1\}$ such that for every YES instance $x \in \{0,1\}^n$, there is a certificate $p \in \{0,1\}^{\mathrm{poly}(n)}$ such that $V(x,p) = 1$; and for every NO ...


15

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, knowing $\mathbf{L}=\mathbf{NL}$ or $\mathbf{L}\neq\mathbf{NL}$ wouldn't imply anything about the $\mathbf{P}$ vs $\mathbf{NP}$ question. (But it's possible that ...


15

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 problems whose answer is YES or NO. (More formally they are all questions of given a string and a language, is the string in the language but that isn't an ...


14

Schaefer's theorem applies only to a specific type of languages, those of the form $\mathrm{SAT}(S)$ for a finite set of relations over the Boolean domain or $\mathrm{CSP}(\Gamma)$ for a finite constraint language over the Boolean domain (the two notations are equivalent; see the Wikipedia page for a description). Any other language is not covered by the ...


13

Sure, you just have to be careful thinking about what it means to have an oracle. The problem comes from an annoying abuse of notation we use in CS: In the statement $P=NP$, $P$ refers to a set of languages. But in the statement $P^A = NP^A$, $P$ refers to a class of Turing Machines (determinstic polytime TMs). You should think of these two $P$s as of ...


12

Oracles are a very general formalization of the idea, "If I could solve $X$ efficiently, I could use that to solve $Y$ efficiently." I accept that it sounds a bit silly to go as far as "If I could solve problem $X$ in constant time, I could use that to solve $Y$ efficiently" but, actually, that doesn't make any real difference at the ...


12

Schaefer's theorem covers a very specific situation: you are given a finite set $\Gamma$ of relations, and are interested in the complexity of $\mathrm{CSP}(\Gamma)$. Schaefer's theorem gives you an algorithm to decide whether this problem is NP-complete or in P. It doesn't cover any other situation. When you translate a problem like integer factorization ...


12

I don't think the theorem is correct. At least, your proof is not correct. The problem is in the second sentences of your proof: Since the problem is NP-complete, any NP problem can be reduced to it in $O(N^r)$ steps, for some $r$. This statement is not correct. There's no guarantee there is a single $r$ that works for every NP problem. You might ...


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