# Questions tagged [p-vs-np]

Questions about or related to P vs. NP

78 questions
Filter by
Sorted by
Tagged with
66 views

### What is the evidence that the worst-case runtime of CDCL is exponential in the length of CNF?

Current SAT solvers have worst-case runtime exponential in the number of variables, leading many computer scientists to speculate that P does not equal to NP. However, the P vs NP problem cares only ...
121 views

### Can Category Theory help us prove P != NP?

Scott Aaronson, in this funny April Fools’ Day post, introduces a fictionalized $P \neq NP$ Proof and, among other things, he says that the proof make use of Higher topos theory to solve the ...
2k views

### What is a natural problem in theory of computation?

In Stephen Cook's paper on the P vs NP problem, he states the following : Feasibility Thesis: A natural problem has a feasible algorithm iff it has a polynomial-time algorithm. My question ...
258 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)?
138 views

### Does P^NP=NP imply NP=coNP? [closed]

If you have it, the proof would be appreciated. Note: P^NP means P with NP oracle
412 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 ...
278 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 ...
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?
699 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 ...
250 views

256 views

329 views

### What is the status of intermediate problems if P is not NP in worst way imaginable?

Assume $P\neq BPP\neq NP$ with caveat that there is a deterministic algorithm for every $NP$ complete problem with input size $n$ bits in $2^{(\log n)^{1+f(n)}}$ arithmetic operations on $\log n$ ...
212 views

### Implications of $\mathsf{P}\neq\mathsf{NP}$ in $\mathsf{BSS}$ model

What are implications of $\mathsf{P}\neq\mathsf{NP}$ in $\mathsf{BSS}$ model to $\mathsf{Turing}$ model and $\mathsf{Valiant's}$ counting complexity model? In opposite direction what are implications ...
573 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 ...
107 views

### what can be said about complexity of “typical” supercomputing programs/ applications? any NP hard?

supercomputers have risen dramatically in their computational powers last few decades due to Moore's law & also increasing parallelism technology in hardware and software. many different types of ...
372 views

### Analogies between VNP and NP

Valiant introduced the class VNP with respect to "arithmetic circuits" over 35 years ago in a "rough" analogy to NP. Recently, there have been major advances in the area of arithmetic circuits eg as ...
285 views

### What's the Impact if proven NP/co-NP=PSPACE on settling P=NP? The future directions it opens to settle/attack P=NP? Remaining classes left outside?

The primary Impact i know would be that: Polynomial Hierarchy collapses to Level 1. NP=co-NP NP=BPP NP=PSPACE BQP=NP and so on.. What are the attack directions it will open for settling P=NP (in ...
721 views

### Is where an oracle B in EXP that $P^B$ $\ne$ $NP^B$? [duplicate]

According to Baker, Gill, Solovey where is an oracle A in EXP, so $P^A$ = $NP^A$. But is there an oracle B in EXP, what $P^B$ $\ne$ $NP^B$?
290 views

### intuition that VP=?VNP is (not?) connected to P=?NP

recently there has been major progress into the VP=?VNP problem for algebraic circuits originated by Valiant, inspiring some optimistic outlook on its eventual or imminent resolution. what is an ...
509 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 ...
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 ...
148 views

### What is known about lower bounds on the algorithm if P=NP

I recall Scott Aaronson making the claim that either $P\neq NP$ or he has superpowers. What reason is there, if any, to believe that it is not the case that any decision procedure has constants (or ...
481 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. ...
827 views

139 views

### Assume that $\mathsf{NP} \subseteq \mathsf{P}/\text{log(n)}$, does it imply that $\mathsf{P} = \mathsf{NP}$? [closed]

I am trying to either prove or refute the claim mentioned in the title. Any ideas ?
860 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]$, ...
494 views

### equivalent way(s) of expressing P=?NP problem in linear programming?

the paper "In defense of the Simplex Algorithm's worst-case behavior" Disser/Skutella  was recently cited on this tcs.se site by saeed on another interesting question. the paper introduces the idea ...
306 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 ...
476 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 ...
239 views

### Can on every instance P = NP? [closed]

I want to ask a question concerning some aspects of the P vs. NP problem. NOTE: Possibly by "popular" standards i am a crank (i tend towards P=NP), but lets focus on the issue (please with a grain of ...
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 ...
803 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 ...