# Tag Info

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,722

### 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 ...
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.3k
Accepted

### Looking for Literature Source for Following idea

It seems that this idea is attributed to Levin (It is called optimal search). I believe this fact is well known. A similar algorithm is described in wikipedia for instance, although using the subset ...
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 ...
• 35.8k
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,090
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.5k
Accepted

### Statements that imply $\mathbf{P}\neq \mathbf{NP}$

A proof system for propositional logic is called polynomially bounded, if every tautology $\varphi$ has a proof in the system of length polynomial in the length of $\varphi$. The statement "There ...
• 4,511

### 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}: \...

### Statements that imply $\mathbf{P}\neq \mathbf{NP}$

Geometric complexity theory (GCT) (also [1]) has not been mentioned yet. its a large ambitious program to connect P vs NP to algebraic geometry. eg a brief synopsis from the survey Understanding the ...
• 10.8k

### Statements that imply $\mathbf{P}\neq \mathbf{NP}$

The following result by Raz (Elusive Functions and Lower Bounds for Arithmetic Circuits, STOC'08) is aimed at $VP\neq VNP$ (and not directly $P\neq NP$), but it might be close enough for the OP: A ...
• 1,899

### Looking for Literature Source for Following idea

The idea of diagonally running all possible Turing machines has been previously used by Leonid Levin in what is now famously called Levins Universal Search. Unfortunately, and contrary to the ...
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,266

### Statements that imply $\mathbf{P}\neq \mathbf{NP}$

there is a somewhat side/more recently studied field of complexity called graph complexity that studies how larger graphs are built out of smaller graphs using AND and OR operations of edges. Jukna ...
• 10.8k
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.5k

### 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, ...

### 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,516

### 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. ...
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
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 ...
• 4,900
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.8k

### 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.2k
Accepted

• 4,400