Questions tagged [p-vs-np]

Questions about or related to P vs. NP

Filter by
Sorted by
Tagged with
57
votes
9answers
24k views

Explain P = NP problem to 10 year old

It is my first question on this site. I am taking a master's course on theory of computation. How you would explain P = NP problem to a 10 year old child and why it has such a monetary reward on it? ...
38
votes
2answers
3k views

Mulmuley's GCT program

It is sometimes claimed that Ketan Mulmuley's Geometric Complexity Theory is the only plausible program for settling the open questions of complexity theory like P vs. NP question. There has been ...
34
votes
6answers
2k views

Why are so few natural candidates for NP-intermediate status?

It is well known by Ladner's Theorem that if ${\mathsf P}\neq \mathsf {NP}$, then there exist infinitely many $\mathsf {NP}$-intermediate ($\mathsf{NPI}$) problems. There are also natural candidates ...
32
votes
7answers
10k views

Should we consider $\mathsf{P} \neq \mathsf{NP}$ a law of nature?

Many experts believe that the $\mathsf{P} \neq \mathsf{NP}$ conjecture is true and use it in their results. My concern is that the complexity strongly depends on the $\mathsf{P} \neq \mathsf{NP}$ ...
29
votes
1answer
1k views

Toy examples for barriers to $P \ne NP$

Are there any toy examples that provide 'essential' insights into understanding the three known barriers to $P = NP$ problem - relativization, natural proofs and algebrization?
29
votes
3answers
1k views

Is NPI contained in P/poly?

It is conjectured that $\mathsf{NP} \nsubseteq \mathsf{P}/\text{poly}$ since the converse would imply $\mathsf{PH} = \Sigma_2$. Ladner's theorem establishes that if $\mathsf{P} \ne \mathsf{NP}$ then $\...
27
votes
5answers
4k views

Implications of unprovability of $P\neq NP$

I was reading "Is P Versus NP Formally Independent?" but I got puzzled. It is widely believed in complexity theory that $\mathsf{P} \neq \mathsf{NP}$. My question is about what if this is ...
26
votes
4answers
2k views

Proofs, Barriers and P vs NP

It is well known that any proof resolving the P vs NP question must overcome relativization, natural proofs and algebrization barriers. The following diagram partitions the "proof space" into ...
26
votes
4answers
2k views

Best known deterministic time complexity lower bound for a natural problem in NP

This answer to Major unsolved problems in theoretical computer science? question states that it is open if a particular problem in NP requires $\Omega(n^2)$ time. Looking at the comments under answer ...
21
votes
6answers
2k views

Statements that imply $\mathbf{P}\neq \mathbf{NP}$

This is sort of an open-ended question - for which I apologize in advance. Are there examples of statements that (seemingly) don't have anything to do with complexity or Turing machines but the ...
19
votes
2answers
1k views

Barriers to show $P=NP$

We all know showing $P\ne NP$ has barriers. We all have studied these barriers because we believe $P\ne NP$. However assume $P=NP$ and there are wise people who believe that possibility exists. If ...
19
votes
4answers
2k views

Chaos and the $P{=}NP$ question

I am interested in learning connections between "chaos," or more broadly, dynamical systems, and the $P{=}NP$ question. Here is an example of the type of literature I am seeking: Ercsey-Ravasz, ...
19
votes
1answer
516 views

Natural candidate against the Isomorphism Conjecture?

The famous Isomorphism Conjecture of Berman and Hartmanis says that all $NP$-complete languages are polynomial time isomorphic (p-isomorphic) to each other. The key significance of the conjecture is ...
18
votes
4answers
2k views

List of theorems stating that P does not equal NP if and only if

I think it would be a good idea to make a list of theorems stating that P does not equal NP if and only if such and such exits, some complexity class is contained in another complexity class and so on ...
18
votes
1answer
2k views

Algorithm whose running time depends on P vs. NP

Is there a known, explicit example of an algorithm with the property such that if $P\neq NP$ then this algorithm doesn't run in polynomial time and if $P=NP$ then it does run in polynomial time?
18
votes
0answers
340 views

$\mathsf{P} \ne \mathsf{P/poly} \cap \mathsf{NP}$? [duplicate]

Assuming $\mathsf{P} \ne \mathsf{NP}$ can we show $\mathsf{P} \ne \mathsf{P/poly} \cap \mathsf{NP}$? Obviously this would be the case if $\mathsf{P} \ne \mathsf{NP}$ and $\mathsf{P/poly} \supset \...
16
votes
1answer
792 views

Gowers "discretized Borel determinacy" approach

Gowers has recently outlined a problem, which he calls "discretized Borel determinacy," whose solution is related to proving circuit lower bounds. Can you provide a summary of the approach that is ...
16
votes
0answers
210 views

What is the background in algebraic geometry and representation theory needed for geometric complexity theory? [duplicate]

I'm a mathematics student in my junior year and I'm interested in computational complexity and specially geometric complexity theory. I'm going to learn algebraic geometry and representation theory ...
14
votes
3answers
964 views

What are natural examples of non-relativizable proofs?

As I understand it, a proof that P=NP or P≠NP would need to be non-relativizable (as in recursion theory oracles). Virtually all proofs seem to be relativizable, though. What are good examples of ...
13
votes
3answers
1k views

Why do computer scientists on the whole work under the assumption that P ≠ NP?

Coming from a math background, it seems interesting to me that on the whole computer scientists tend to work under the assumption that $P \neq NP$. While there is no proof either way, generally, ...
12
votes
10answers
2k views

Resources to learn about the P vs. NP problem

I was recently reminded about the $\mathsf{P}$ vs. $\mathsf{NP}$ problem as explained by Stephen A. Cook on Clay Mathematics Institute. It has piqued my interest and I would like to learn more about ...
12
votes
2answers
1k views

Reducing P vs. NP to SAT

The following question uses ideas from cryptography applied to complexity theory. That said, it is a purely complexity-theoretic question, and no crypto knowledge whatsoever is required to answer it. ...
12
votes
2answers
528 views

Looking for Literature Source for Following idea

I am quite certain that I am not the first to entertain the idea that I am going to present. However, it would be helpful if I can find any literature related to the idea. The idea is to construct a ...
12
votes
1answer
469 views

Optimal NP solvers

Fix $X \subset \lbrace 0,1 \rbrace^* \times \lbrace 0,1 \rbrace^*$ an NP-complete search problem e.g. the search form of SAT. Levin search provides an algorithm $L$ for solving $X$ which is optimal in ...
12
votes
1answer
791 views

L/P/PSpace vs P/NP

in 1979 Hopcroft/ Ullman wrote that L ⊆ P ⊆ NP ⊆ PSpace is known but L ⊊ PSpace is the only proper (& trivial) containment known although all are conjectured to be proper containments, and "where ...
11
votes
2answers
2k views

On the provability of P versus NP

First of all, my understanding on Gödel's incompleteness theorem (and formal logic in general) is very naive, also is my knowledge on theoretical computer science (meaning only one graduate course ...
11
votes
2answers
3k views

What is a natural problem in theory of computation?

In Stephen Cook's paper on the P vs NP problem,[1] he states the following [2]: Feasibility Thesis: A natural problem has a feasible algorithm iff it has a polynomial-time algorithm. My question ...
11
votes
3answers
703 views

Recent publications on NP ?= coNP question

I am interested in the question of whether NP is equal to coNP or not. I'd much appreciate some advice on good publications to read on the topic. For the record, I know that this question is ...
9
votes
2answers
1k views

Baker Gill Solovay $P^B \ne NP^B$ relativization, what class is $B$ in?

A recent question asks whether relativization is well-defined. This question wonders how to put one use of it on firmer ground. In the BGS 1975 proof that there exists a language $B$ such that $...
9
votes
3answers
740 views

Could there be an extremely large hidden subset of Polynomially solvable problems within NP-Complete problems?

Suppose P != NP. We know that we can make easy instances of 3-SAT at any time. We can also generate what we believe to be hard instances (because our algorithms can't solve them quickly). Is there ...
9
votes
0answers
319 views

What would be the consequences if all _infinite_ NP-complete languages are p-isomorphic?

The famous Isomorphism Conjecture of Berman and Hartmanis says that all $NP$-complete languages are polynomial time isomorphic ($p$-isomorphic) to each other. It has been an early attempt (published ...
9
votes
0answers
499 views

Assigning probability to membership in an NP-complete language

Motivation Assuming $\mathsf{P}\ne\mathsf{NP}$, it is impossible to efficiently decide membership in an NP-complete language. I would like to assign probability to such membership, in some sense. ...
9
votes
0answers
256 views

Are there sampNP-intermediate problems?

I approximately copied the brief "introduction" to average-case complexity theory of NP from my previous question. However, this question is completely different, so please read on It is conjectured ...
8
votes
3answers
2k views

P vs NP: Instructive example of when Brute Force search can be avoided

To be able to explain the P vs NP problem to non-mathematicians I would like to have a pedagogical example of when Brute Force-search can be avoided. The problem should ideally be immediately ...
8
votes
1answer
293 views

Two DFA intersection emptiness connections to SETH & L vs P

(re "fine grained complexity") Wehar has proved that Two DFA intersection emptiness in $O(n^{2-\epsilon})$ time → SETH false. does anyone see any particular key proof difficulty, challenge, ...
8
votes
1answer
381 views

Is $\mathsf{P} = \mathsf{NP}$ relative to a universal predictor?

Consider any language $L$. Define $s(L) \in {\lbrace 0, 1 \rbrace}^\omega$ (an infinite sequence of bits) by the recursive formula $$s(L)_n=\chi_L(s(L)_{<n})$$ Here $\chi_L$ is the characteristic ...
7
votes
2answers
2k views

P vs. NP and Pseudorandom Bit Generators

According to an article on pseudorandom number generators (PRNG) by Jeff Lagarias, he states that trying to prove that a PRNG is unpredictable (secure) is just "as hard" as trying to prove that P!=NP. ...
7
votes
2answers
311 views

NPI-candidate hereditary graph property?

A graph property is called hereditary if it is closed with respect to deleting vertices. There are many interesting hereditary graph properties. Moreover, a number of nontrivial general facts are ...
7
votes
1answer
286 views

Is there a relation between BBH (black box hypothesis) and SETH (strong exponential time hypothesis)?

Is there a relation between BBH (black box hypothesis) and SETH (strong exponential time hypothesis)?
7
votes
1answer
620 views

Public-key encryption without the assumption that $P \neq NP$

I'm not talking about the RSA, El-gamal, nor any specific encryption scheme. Rather, my question, as related to this and this threads, is why the idea of Public-Key encryption scheme cannot be secure ...
6
votes
1answer
673 views

Is "two or zero" matching in a bipartite graph NP complete?

I have this problem, which I haven't seen before in the literature: given a bipartite graph and a natural number $k$, can we select at least $k$ of the edges such that each left-hand vertex is ...
6
votes
1answer
1k views

Do we know that the P vs. NP question isn't affected by Gödels incompleteness theorem? [duplicate]

Possible Duplicate: Implications of unprovability of $P\neq NP$ I shortly came across Gödels incompleteness theorem again and I wondered, since so much time has been spent on trying to answer ...
6
votes
1answer
301 views

Is Murphy's Law of Complexity Theory consistent? What separations/collapses does it imply?

A decade ago I observed what I dub "Murphy's Law of Complexity Theory": whenever a new separation or collapse is discovered, the question is answered in the direction that makes $P\overset?=NP$ most ...
6
votes
0answers
822 views

What is the status of Vladimir Romanov's proof that P=NP? [closed]

A couple of months ago there was a minor hubbub about a paper published on ArXiV by V. F. Romanov titled Non-Orthodox Combinatorial Models Based on Discordant Structures which claimed to give a ...
5
votes
1answer
428 views

Is there a counterexample to this work?

Is there a counterexample to this claim https://arxiv.org/abs/1610.00353? They claim a $O(n^6)$ LP model with simulations to support. I think asking validity is not a reasonable problem. However ...
5
votes
2answers
268 views

ETH-Hardness of $Gap\text-MAX\text-3SAT_{c}$

The PCP theorem can be stated like this : There is a polynomial time reduction from SAT to $Gap\text-MAX\text-3SAT_{c}$ i.e. there is a reduction that maps an instance $\phi$ of SAT to an instance $...
5
votes
3answers
1k views

If SAT is in PCP, for some constant q, then P = NP

I have seen this statement before, but I haven't really seen a proof of it: If $SAT\in PCP_{1,2^{−q}}[\log(n),q]$, for some constant $q$, then $P = NP$. Now, if $SAT\in PCP_{1,2^{−q}}[\log(n),q]$, ...
5
votes
1answer
231 views

Questions about P vs NP and geometric complexity theory

Reading through various papers on geometric complexity theory (GCT), there is one thing, which pops up, while claimed in various places, that it is an approach to P vs NP, all the results seems to ...
5
votes
0answers
167 views

Converse to natural proofs theorem?

Natural proofs paper shows 'if there is a natural property not possessed by any function in P/poly then there is no $2^{n^\epsilon}$-hard PRG'. Is it easy to see the converse 'if there is no $2^{n^\...
5
votes
0answers
215 views

Non-uniform average-case complexity of NP

It is conjectured that NP-complete problems are hard not only in the worst case but also in the typical case. Formally, given a language $S \in \lbrace 0,1 \rbrace^*$ and for each $n$ a probability ...