Questions tagged [p-vs-np]
Questions about or related to P vs. NP
92
questions
-4
votes
0
answers
55
views
would statistical randomness disprove P=NP
I saw a proof that claimed if the 3sat problem was statistically random which by definition means there are no patterns, then a deterministic turing machine could not possibly solve it more ...
-6
votes
0
answers
92
views
I found a fascinating solution to P=NP on academia.edu, where he creates an inherently undeterministic problem using statistical randomness
for background I just started researching computational complexity, so I have major gaps in understanding. I am not 100% sure if this guy is correct, but I can't seem to see why he would be wrong. ...
0
votes
2
answers
148
views
Bottom up TSP solution?
I'm not sure if this is something new or if I'm just not getting previous efforts. TSP can be thought of as a list of weighted links and nodes. If one takes the Nearest Neighbor (NN) of every node and ...
0
votes
1
answer
145
views
Complexity of solving a higher-order degree polynomial equation? P-problem or NP-problem or neither?
I am a mathematician and I am very new to theoretical computer science.
The definition of P/NP problem I found in wiki is that:
P is the set of decision problems solvable in polynomial time by a ...
10
votes
2
answers
1k
views
Formulating P vs NP without Turing machines
Computability in terms of Turing machines is equivalent to computability described by computable functions (based on primitive recursive functions, introducing the $\mu$-operator and so on). Is there ...
1
vote
0
answers
71
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 ...
user69160
0
votes
1
answer
322
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 ...
- 101
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
96
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
244
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
72
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$
...
- 139
1
vote
0
answers
147
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.8k
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
385
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,465
5
votes
1
answer
360
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 ...
- 900
2
votes
0
answers
561
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
14
votes
3
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 ...
- 143
8
votes
1
answer
315
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)?
- 91
-3
votes
1
answer
321
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
5
votes
1
answer
450
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.8k
6
votes
1
answer
320
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.8k
2
votes
1
answer
430
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,243
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,572
-3
votes
1
answer
126
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.8k
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.8k
0
votes
1
answer
352
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
550
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
220
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.8k
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^\...
- 12.8k
5
votes
2
answers
293
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
216
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
359
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 ...
- 11.3k
2
votes
0
answers
132
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,100
6
votes
1
answer
725
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
327
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, ...
- 11k
22
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,743
1
vote
0
answers
187
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
335
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.8k
4
votes
1
answer
228
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
951
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 ...
- 11k
-2
votes
1
answer
127
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 ...
- 11k
4
votes
1
answer
450
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 ...
- 11k
1
vote
0
answers
427
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 ...
- 793
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
410
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 ...
- 11k
13
votes
2
answers
628
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 ...
- 425
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 ...