# Questions tagged [p-vs-np]

Questions about or related to P vs. NP

22 questions
Filter by
Sorted by
Tagged with
3k 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 ...
• 10.6k
25k 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? ...
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 ...
• 4,031
5k 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 ...
• 407
567 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 ...
• 11.4k
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 ...
1k 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 ...
• 241
1k views

• 2,151
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 ...
• 4,031
3k 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 ...
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 ...
• 2,598
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. ...
• 16.5k
787 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 ...
• 745
429 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 ...
• 2,151
317 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)?
733 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 ...
242 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 ...
• 2,151
553 views

### P/poly vs NP separation based on circuit trees instead of DAGs

there are various theorems that relate major complexity class separations to circuit family DAGs sizes, in particular for P/poly vs NP. in contrast, are there theorems/conjectures that relate P/...
• 11k
I want to ask a question concerning some aspects of the P vs. NP problem. There are some results that people use to support a preference / belief about the conjecture $P \neq NP$ (e.g. separation of P ...