Questions tagged [p-vs-np]

Questions about or related to P vs. NP

22 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
12 votes
0 answers
394 views

Invisible electric fence even if P = NP?

Scott Aaronson has suggested that one argument in favor of $\mathsf{P} \ne \mathsf{NP}$ is that there seems to be an invisible electric fence separating $\mathsf{NP}$-complete problems from problems ...
Timothy Chow's user avatar
  • 7,550
9 votes
0 answers
361 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 ...
Andras Farago's user avatar
9 votes
0 answers
514 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. ...
Vanessa's user avatar
  • 2,151
9 votes
0 answers
265 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 ...
Vanessa's user avatar
  • 2,151
7 votes
0 answers
1k views

Does L=P imply any new complexity class separations?

If L=P then P is not equal to PSPACE. This follows from PSPACE properly containing L. I am wondering if L=P implies any stronger separation between complexity classes? Does it imply P is properly ...
Anonymous's user avatar
  • 4,041
6 votes
0 answers
183 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^\...
Turbo's user avatar
  • 12.9k
5 votes
0 answers
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 ...
Vanessa's user avatar
  • 2,151
3 votes
0 answers
224 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$) ...
Turbo's user avatar
  • 12.9k
3 votes
0 answers
256 views

Does $P\neq NP$ imply any larger separation?

I've asked a similar question in cs.se, but didn't get a satisfying answer. Assuming $P\neq NP$, what can we say about the runtime of any algorithm for an $NP$-complete problem? Obviously, it means $...
R B's user avatar
  • 9,448
2 votes
0 answers
606 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 biggest ...
Yamar69's user avatar
  • 684
2 votes
0 answers
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 ...
Samuel Schlesinger's user avatar
2 votes
0 answers
133 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 ...
Matt Groff's user avatar
  • 2,100
1 vote
0 answers
77 views

Consequences of a $Parity$ $P$-problem being reducible to a sparse language?

$Parity$ $P$ is the class where an $NP$-machine answers $YES$ if and only if the number of accepting paths of that turing machine is odd. With regards to the $P$ vs $NP$ question, there is a theorem ...
user avatar
1 vote
0 answers
473 views

Is it known that P $\neq$ NP implies BQP $\neq$ NP?

Pretty much the title. Is there any result that shows that $P \neq NP \Rightarrow BQP \neq NP$. I think it's pretty clear that $BQP \neq NP \Rightarrow P \neq NP$, as $P$ is a subclass of $BQP$. But ...
Loic Stoic's user avatar
1 vote
0 answers
153 views

Relation between BSS and Turing models

$P_\mathbb R$ is the set of languages decidable in polynomial time over the real $BSS$ machine defined in https://en.wikipedia.org/wiki/Blum%E2%80%93Shub%E2%80%93Smale_machine. Let $0-1-P_\mathbb R=\{...
Turbo's user avatar
  • 12.9k
1 vote
0 answers
189 views

Consequences of VP = VNP on randomness

According to the answers in posting it is possible that $\mathsf{VP} = \mathsf{VNP}$ and $\mathsf{P} \neq \mathsf{NP}$ are simultaneously correct. $\mathsf{VP} = \mathsf{VNP}$ implies $\mathsf{P/...
user avatar
1 vote
0 answers
440 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 ...
TheoryQuest1's user avatar
1 vote
0 answers
418 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.[1] what is an ...
vzn's user avatar
  • 11k
1 vote
0 answers
153 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 ...
Alex R's user avatar
  • 161
1 vote
0 answers
247 views

What are the consequences of a ${\bf O}$(m) algorithm for SAT

We are given a Boolean formula $F$ in conjunctive normal form with $n$ variables and $m$ clauses and we would like to know if there exists at least one assignment to the $n$ variables that makes $F$ ...
user avatar
0 votes
0 answers
74 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$ ...
Omid Yaghoubi's user avatar
0 votes
0 answers
91 views

What are the capabilities of current Boolean Satisfiability Solvers?

I am wondering how well current Boolean Satisfiability solvers are able to perform — for example, are the best SATsolvers able to solve problems from SATlib?
Nat Kar's user avatar