# Tag Info

215

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

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

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

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

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

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

A very nice read here is , 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$. ...

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

Copying my answer to a similar question on Stack Overflow: The easiest way to explain P v. NP and such without getting into technicalities is to compare "word problems" with "multiple choice problems". When you are trying to solve a "word problem" you have to find the solution from scratch. When you are trying to solve a "multiple choice problems" you have ...

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

12

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 isn't necessary to plug in all possible values and sketch how to arrive at an $O^*((2^k-1)^{n/k})$ time algorithm, where $k$ is the number of clauses. $O^*$ '...

11

This is still an open question; UP is not known to be equivalent to NP. In the paper "NP Might Not Be As Easy As Detecting Unique Solutions," Beigel, Burhman and Fortnow construct an oracle under which P contains UP but P is still not equivalent to NP.

11

Even without P=NP, today's computers are unbelievable powerful. 12873891274647018937561708356916501047777612653914909670721635802187 can be factored by a single computer in less than a second. For harder tasks like synthesizing the electric layout of a chip from a higher level description of its functions, or correcting photomasks to compensate artifacts ...

11

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 other methods, you only asked if they could be applied to NP complete problems. The answer is yes, with some success and this has been known for decades and there ...

11

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 of the problem usually grows polynomially. For example, when you reduce a HAMPATH on a graph with $n$ nodes to SAT, the resulting formula has size of \$\Theta(n^...

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