# Questions tagged [p-vs-np]

Questions about or related to P vs. NP

83 questions
Filter by
Sorted by
Tagged with
1 vote
199 views

### What if NP = coNP?

Are there any major implications of NP = coNP (if true) the way there would be if P=NP? I'm thinking of real-world implications analogous to the encryption-pocalypse (excuse the drama) that would ...
• 33
67 views

### Number of outputs produced by levin search variant (SIMPLE)

Let $f$ be an inverting problem. If there is an algorithm A that invert $f$ in time $t(n)$, then the SIMPLE algorithm below invert $f$ in time $c.t(n)$ where $c$ is a constant depending only on $A$ ...
1 vote
137 views

• 3,221
125 views

### What are some known methods for showing that a class has no complete problems?

The only way that I know of is the way that you can show that $RE \cap coRE$ does not via diagonalization. Mostly curious because if $NP \cap coNP$ has no complete problems then $P \neq NP$. I tried ...
• 1,552
124 views

### What is wrong with this procedure to convert quadratic programming to convex quadratic programming?

Consider the feasibility quadratic program with constraint $$\sum_{i=1}^nc_{i1}x_{i}\leq \ell_1$$ $$\vdots$$ $$\sum_{i=1}^nc_{it}x_{i}\leq \ell_t$$ \sum_{i,j=1}^na_{ij}x_{i}x_{j}+\sum_{i=1}^nb_{i}x_{...
• 12.5k
221 views

### Is there any known strategy that avoids circuits and that respects believed separations to prove $P$ is not $NP$?

Vinay Deolalikar's approach tried to randomness is not strong enough, Blum's proof tried to show $P/poly$ is not strong enough, Mulmuley's and Smale's approach (while not enough to show $P\neq NP$) ...
• 12.5k
328 views

### ${\bf NP} \not = {\bf E}$ and ${\bf PSPACE} \not = {\bf E}$

We know that ${\bf NP} \subseteq {\bf PH} \subseteq {\bf PSPACE}$. We also know that ${\bf E} \subset {\bf EXP}$, where ${\bf E} = \cup_c DTIME[2^{cn}]$ and ${\bf EXP} = \cup_c DTIME[2^{n^c}]$. It ...
529 views

### Can one prove the discovery of a P versus NP solution without actually revealing it?

Suppose a person has proved that P≠NP. He wants to let the world know that he has solved the P versus NP problem but does not want to reveal that he has proved P≠NP as opposed to P=NP. Is there any ...
1 vote
191 views

### Unambiguous SAT and sparse languages

What is the consequence if there are only polynomially many 'yes' classes of instances of a language that is polynomial time reducible from a problem equivalent to UnambiguousSAT (such as possibly ...
• 12.5k
178 views

• 243
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, ...
• 273
213 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 ...
• 269
325 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 ...
• 10.8k
128 views

### What would faster Fourier Transform(FFT?) and/or multiplication algorithms imply?

There are many problems which have implications on P vs. NP and other complexity classes. Supposing that we're interested in Fourier transforms and/or multiplication algorithms, do faster Fourier ...
• 2,080
688 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 ...
309 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, ...
• 10.9k
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, ...
• 3,703
168 views

• 10.9k