20
votes
Accepted
Is there a counterexample to this work?
Predecessor versions of this paper have been around for more than 15 years. I remember that there were counter-examples to the first versions, then first revisions, counter-examples to the first ...
- 5,742
18
votes
Barriers to show $P=NP$
Mihalis Yannakakis has shown that the traveling salesman problem cannot be solved in polynomial time by using a symmetric linear program.
See the paper Expressing combinatorial optimization problems ...
17
votes
Accepted
Algorithm whose running time depends on P vs. NP
If you assume that $P=^?NP$ is provable in PA (or ZFC), a trivial example is the following:
...
- 22.4k
16
votes
Accepted
What is a natural problem in theory of computation?
To be clear, it's not meant to be formalizable. It's not a theorem, it's an observation about the world -- it's okay if "natural" is subjective here. For analogy, if someone says "differentiation is ...
- 7,140
15
votes
Accepted
Analogies between VNP and NP
The basic idea is that summing over all Boolean strings (VNP) is like counting the solutions to an NP problem. Even from this perspective, one sees that VNP is more like #P than NP. This is also true ...
- 36.2k
14
votes
Proofs, Barriers and P vs NP
Contrary to some claims earlier in this thread, algebrization in the sense of Aaronson & Wigderson is not known to subsume relativization. For example,
$$\tag{$\dagger$}(\exists \mathcal{C}: \...
14
votes
Accepted
Why do computer scientists on the whole work under the assumption that P ≠ NP?
As a rule of thumb, for any unsolved problem people tend to conjecture the statement that starts with a universal quantifier - since if it started with an existential one, then one would expect to ...
- 13.8k
13
votes
Accepted
Did Jinliang Wang solve the P versus NP problem?
No, the pruning in the paper doesn’t work. For example, consider a graph on four nodes where two nodes have distance 1 while the other two have distance 101, with all other edges having distance 100. ...
- 1,697
9
votes
Accepted
Is "two or zero" matching in a bipartite graph NP complete?
The answer here seems to imply there is a more general result. For this particular case, here is a self contained way to reduce the problem to maximum weight perfect matching. Assume $k$ is even.
...
- 4,306
9
votes
Accepted
Is there a relation between BBH (black box hypothesis) and SETH (strong exponential time hypothesis)?
Adding to Sasha's answer. Roughly speaking, BBH posits that every property of functions that is hard to decide with only query access to the function (black box access) is also hard to decide when you'...
- 26.7k
8
votes
List of theorems stating that P does not equal NP if and only if
Here is a result from descriptive complexity theory:
$P \ne NP$ if and only if some second order property is not expressible using first order logic plus least fixed point.
Reference:
Immerman, ...
- 20.7k
8
votes
Implications of unprovability of $P\neq NP$
As proved in this paper:
http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-get.cgi/1991/CS/CS0699.revised.pdf
If $P \neq NP$ can be shown to be independent
of Peano Arithmetic, then NP has extremely-...
- 1,526
7
votes
List of theorems stating that P does not equal NP if and only if
Ladner theorem can be stated as:
$P \ne NP$ if and only if there exists an incomplete set in $NP-P$.
Incomplete set is a set that is not complete for $NP$ under many-one polynomial time reductions.
...
- 20.7k
7
votes
Accepted
L/P/PSpace vs P/NP
The only known proper containment is still $L \subsetneq PSPACE$, though they are all widely believed to be different. All the rest are still wide-open.
The recent work on ``Fine-Grained Complexity",...
- 111
7
votes
Accepted
Two DFA intersection emptiness connections to SETH & L vs P
The "inverse" is almost the same as
SAT is solvable in $O(2^{(1-\epsilon)n})$ time implies the intersection problem is solvable in
$O(n^{2-\epsilon})$ time.
To show this, it seems that you would ...
- 5,005
7
votes
Accepted
Chaos and the $P{=}NP$ question
the paper you cite by Ercsey-Ravasz, Toroczkai is very crosscutting; it fits in with/ touches on several lines of NP complete problem/ complexity/ hardness research. the connection to statistical ...
- 10.9k
7
votes
Barriers to show $P=NP$
Not much of a barrier, but it's worth noting that a lot of Proof Complexity research involves finding lower bounds to the size of proofs of propositional statements in certain settings.
For example, ...
- 13.4k
6
votes
Accepted
${\bf NP} \not = {\bf E}$ and ${\bf PSPACE} \not = {\bf E}$
${\bf E} \not = {\bf NP}$ does not imply ${\bf E} \subset {\bf NP}$ nor ${\bf NP} \subset {\bf E}$. Similarly, ${\bf E} \not = {\bf PSPACE}$ does not imply ${\bf E} \subset {\bf PSPACE}$ nor ${\bf ...
- 2,579
6
votes
Chaos and the $P{=}NP$ question
There is a relatively recent research trend (15 years or so) of mixing statistical physics of disordered systems and discrete, combinatoric, optimization problems. The link is through the Boltzmann ...
- 161
5
votes
Chaos and the $P{=}NP$ question
Unfortunately it's behind a paywall so I'm unable to view that paper but from reading the abstract it bears at least a superficial similarity to some "cartoon pictures" that I've seen on survey ...
- 2,776
5
votes
P vs. NP in a logic with a random oracle
Yes on Question 1 (assuming ZFC is consistent). You don't need $f$ to be random exactly, any $f$ will do. And for the proof you need to also use the fact that there is an oracle $h$ with NP$^h=$P$^h$.
- 4,435
4
votes
Accepted
ETH-Hardness of $Gap\text-MAX\text-3SAT_{c}$
I think the best known result is that the blow-up can be quasi-linear (the new instance has size $n\cdot(\log n)^{O(1)}$). This is given in Dinur's 2007 paper (Thm 8.1), which is also cited by the ...
- 3,156
4
votes
What is a natural problem in theory of computation?
It roughly boils down to whether the problem definition could be circular:
An artificial problem is one constructed to fill its class criteria.
A natural problem does not rely on its method of ...
- 51
3
votes
Accepted
Does P^NP=NP imply NP=coNP?
Yes, it implies. $P^{NP}$ is the set of languages that are Turing reducible to $NP$ (for example, to $SAT$, or any other $NP$-complete problem). If we take a Boolean formula $F$, then $F\in UNSAT$ ...
- 10.8k
3
votes
Is Murphy's Law of Complexity Theory consistent? What separations/collapses does it imply?
A counterexample to this Murphy's Law could actually be the famous paper
Baker, Theodore; Gill, John; Solovay, Robert, Relativizations of the $\cal P=?\cal N\cal P$ question, SIAM J. Comput. 4, 431-...
- 4,435
3
votes
Implications of $\mathsf{P}\neq\mathsf{NP}$ in $\mathsf{BSS}$ model
$\newcommand\Ptime{\mathsf P} \newcommand\NP{\mathsf{NP}} \newcommand\poly{\mathsf{poly}}$
It is known that $\Ptime/\poly \neq \NP/\poly \implies \Ptime_{\mathbb C}\neq \NP_\mathbb{C}$ [1] where the ...
- 4,410
3
votes
Accepted
What is wrong with this procedure to convert quadratic programming to convex quadratic programming?
The constraint $x_i x_j = y_{ij}$ isn't convex. Indeed, even the simpler constraint $ab = 8$ isn't convex. Let $C = \{(a,b) : ab = 8\}$. Then $(4,2),(2,4) \in C$ but $(3,3) \notin C$.
- 14.2k
3
votes
Can one prove the discovery of a P versus NP solution without actually revealing it?
Or Meir’s comment is almost but not quite right, since it would be satisfied by a proof that P vs. NP is not independent even if the prover didn’t know which. A corrected version is “X is either the ...
- 3,221
3
votes
Chaos and the $P{=}NP$ question
This paper, Polynomial-time solution of prime factorization and NP-complete problems with digital memcomputing machines, claims an efficient algorithm for NP-complete problems. Digital memcomputing ...
- 20.7k
3
votes
Accepted
Questions about P vs NP and geometric complexity theory
The short answer is no these are not known, though they are certainly not out of the question. There are no direct implications known to P vs NP, and we do not even have a conjecture (let alone ...
- 36.2k
Only top scored, non community-wiki answers of a minimum length are eligible