Hot answers tagged

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 ...
user avatar
  • 29.1k
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)$. ...
user avatar
  • 12.3k
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 ...
user avatar
  • 594
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 \...
user avatar
  • 9,325
36 votes
Accepted

What would be the real-world implications of a constructive $P=NP$ proof?

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 ...
user avatar
  • 29.1k
33 votes

What would be the real-world implications of a constructive $P=NP$ proof?

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 ...
user avatar
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-...
user avatar
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 ...
user avatar
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, ...
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. ...
user avatar
  • 785
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 ...
user avatar
  • 29.1k
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 ...
user avatar
  • 140k
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 ...
user avatar
  • 4,889
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 ...
user avatar
  • 409
18 votes

What would be the real-world implications of a constructive $P=NP$ proof?

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 (...
user avatar
  • 22.1k
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 ...
user avatar
  • 140k
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, ...
user avatar
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 ...
user avatar
14 votes
Accepted

Why do Shaefer's and Mahaney's Theorems not imply P = NP?

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 ...
user avatar
13 votes
Accepted

Why is this argument for $P\neq NP$ wrong?

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 ...
user avatar
  • 4,009
12 votes

How is it valid to use oracles in mathematical arguments?

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 ...
user avatar
12 votes

Why does Schaefer's theorem not prove that P=NP?

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 ...
user avatar
12 votes
Accepted

Is my theorem about $P \neq NP$ correct?

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 ...
user avatar
  • 140k
12 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 ...
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 ...
user avatar
  • 6,978
11 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 ...
user avatar
  • 223
11 votes
Accepted

If one shows that UNIQUE k-SAT is in P, does it imply P=NP?

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 ...
user avatar
  • 7,833
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 ...
user avatar
  • 10.8k
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:...
user avatar
10 votes

How is it valid to use oracles in mathematical arguments?

There are several applications to oracles. First, there is usage in proving lower bounds (i.e. Turing reductions): if you know that a problem $L$ cannot be solved within some complexity (or ...
user avatar
  • 16.2k

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