Questions tagged [p-vs-np]
Questions about or related to P vs. NP
86
questions
0
votes
0
answers
103
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 ...
1
vote
1
answer
1k
views
Did Jinliang Wang solve the P versus NP problem?
Recently, I saw a paper on the Internet [1]. Did the author of this paper, Jinliang Wang, solve the P versus NP problem?
Reference
[1] Wang, J. L. (2018) Fast Algorithm for the Travelling Salesman ...
- 121
-3
votes
1
answer
89
views
Why if non determinism adds no power at all to DFAs or to Turing machines, why is it that most people beleieve P != NP [closed]
During Theory of Computation or Automata Theory or the equivalent class at my University, I was shown that non deterministic and deterministic automata can solve the exact same set of problems, then ...
1
vote
1
answer
214
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
0
votes
0
answers
71
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$
...
- 129
1
vote
0
answers
139
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=\{...
- 12.6k
0
votes
0
answers
89
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?
- 1
12
votes
0
answers
375
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 ...
- 7,093
5
votes
1
answer
308
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 ...
- 841
2
votes
0
answers
458
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 ...
- 684
12
votes
2
answers
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 ...
- 123
7
votes
1
answer
308
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)?
- 81
-2
votes
1
answer
302
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
- 11
5
votes
1
answer
445
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 ...
- 12.6k
6
votes
1
answer
314
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 ...
18
votes
1
answer
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?
- 317
20
votes
2
answers
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 ...
- 12.6k
2
votes
1
answer
381
views
P vs. NP in a logic with a random oracle
Choose a random oracle $f : \{0,1\}^\ast \to \{0,1\}$, and define the logic $ZFC^f$ by adding a fresh symbol $g$, an axiom that $g$ has the correct type, and one axiom $g(s) = f(s)$ for each $s \in \{...
- 3,223
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 ...
- 1,562
-3
votes
1
answer
125
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.6k
3
votes
0
answers
222
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.6k
0
votes
1
answer
334
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 ...
3
votes
1
answer
533
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
1
answer
201
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.6k
5
votes
0
answers
179
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^\...
- 12.6k
5
votes
2
answers
285
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 $...
- 243
13
votes
3
answers
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
16
votes
0
answers
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
9
votes
0
answers
348
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
2
votes
0
answers
130
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
6
votes
1
answer
703
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 ...
- 163
8
votes
1
answer
322
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
20
votes
4
answers
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
1
vote
0
answers
179
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/...
user34945
-2
votes
1
answer
334
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$ ...
- 12.6k
4
votes
1
answer
225
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 ...
user34945
12
votes
1
answer
918
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 ...
- 10.9k
-2
votes
1
answer
124
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 ...
- 10.9k
4
votes
1
answer
441
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 ...
- 10.9k
1
vote
0
answers
420
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 ...
- 783
1
vote
1
answer
1k
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$?
- 13
1
vote
0
answers
394
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 ...
- 10.9k
13
votes
2
answers
616
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 ...
- 415
23
votes
6
answers
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 ...
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 ...
- 161
9
votes
0
answers
513
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.
...
- 2,151
8
votes
2
answers
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 $...
- 10.9k
3
votes
0
answers
252
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 $...
- 9,368
0
votes
1
answer
140
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 ?
- 135
5
votes
3
answers
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]$, ...
- 649