Hot answers tagged

361

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 ...


178

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{...


94

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 ...


76

I'd say the most well known barriers to solving $P=NP$ are Relativization (as mentioned by Ran G.) Natural Proofs - under certain cryptographic assumptions, Rudich and Razborov proved that we cannot prove $P\neq NP$ using a class of proofs called natural proofs. Algebrization - by Scott Aaronson and Avi Wigderson. They prove that proofs that algebrize ...


68

It is known that P$\subseteq$NP$\subset$R, where R is the set of recursive languages. Since R is countable and P is infinite (e.g. the languages $\{n\}$ for $n \in \mathbb{N}$ are in P), we get that P and NP are both countable.


55

Note: I haven't checked the answer carefully yet and there are missing parts to be written, consider it a first draft. This answer is meant mainly for people who are not researchers in complexity theory or related fields. If you are a complexity theorist and have read the answer please let me know if you notice any issue or have an idea about to improve the ...


55

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 ...


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 ...


34

Maybe the most common technique that cannot be used is relativization, that is, having a TM with oracle access. The impossibility follows from a paper by Theodore Baker, John Gill, Robert Solovay who show the existence of two oracles (languages), $A$ and $B$ such that $\text{P}^A = \text{NP}^A$ and $\text{P}^B \ne \text{NP}^B$. Thus, if some proof for, ...


34

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

To put it more concretely, if I have an approach to prove P≠NP and if I could construct oracles to make a situation like above happen, why does it make my method invalid? Note that the latter “if” is not a condition, because Baker, Gill, and Solovay already constructed such an oracle. It is just a mathematical truth that (1) there exists an oracle relative ...


30

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 ...


30

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 ...


27

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 ...


26

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!


24

Are there any known problems in NP (and not in P) that aren't NP Complete? My understanding is that there are no currently known problems where this is the case, but it hasn't been ruled out as a possibility. No, this is unknown (with the exception of the trivial languages $\emptyset$ and $\Sigma^*$, these two are not complete because of the definition of ...


24

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 ...


22

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 ...


21

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

There are already good answers, but I would like to add a few small points. Assume that we have a technique to solve problems, e.g. diagonalization. Assume that we want to show that the technique cannot solve a specific problem e.g. $\mathsf{P}$ vs. $\mathsf{NP}$. How can be show this? Before going further, note that a technique like diagonalization is not ...


19

A Turing machine, it must be remembered, is a kind of flowchart. So is the structure of a computer program generally. So turning "a flowchart" into a formal answer to the problem should be fairly easy, if it actually did work. Indeed, if one started with a terribly formal answer to P versus NP, most computer scientists would try to find a formulation of ...


19

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 ...


17

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 ...


17

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 $\...


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

"No", you can use "basic English". If you succeeded, you would have created a constructive proof. Proofs in mathematics are often a mix of "basic English" as you call it and mathematical formulae, but they need not contain either to be a valid proof. Suppose you have such a flowchart, what you need to prove—i.e. argue—is, that your algorithm ...


16

Let $\mathrm{A}$ and $\mathrm{B}$ be two complexity classes. A separation ($\mathrm{A} \neq \mathrm{B}$) or collapse ($\mathrm{A} = \mathrm{B}$) is said to relativize if for all oracles $\mathrm{O}$ we have $\mathrm{A}^\mathrm{O} \neq \mathrm{B}^\mathrm{O}$ or $\mathrm{A}^\mathrm{O} = \mathrm{B}^\mathrm{O}$ respectively. The Baker-Gill-Solovay proof tells us ...


16

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\...


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 ...


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