# 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,772
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,615

### 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: ...
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 ...
• 14k

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

### Formulating P vs NP without Turing machines

$\def\cat{_\smile}$Sure. By a classical result of Cobham, the set FP of polynomial-time functions can be described as the smallest set of functions $f\colon(\{0,1\}^*)^n\to\{0,1\}^*$ ($n\in\mathbb N$) ...
• 17.4k
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,735

### Implications of unprovability of $P\neq NP$

As proved in the paper "On The Independence of P Versus NP" by S. Ben-David and S. Halevi: If $P \neq NP$ can be shown to be independent of Peano Arithmetic, then NP has extremely-close-to-...
• 1,606
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,439
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'...
• 27.5k

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

Accepted

### What if NP = coNP?

This got a bit too long for a comment, I might edit this to provide a more coherent answer at a later point. There is this answer to Is it possible to construct an encryption scheme for which breaking ...
• 920
1 vote

### Bottom up TSP solution?

"If one takes the 2 nearest neighbors of every node and adds them all up, that is a theoretical minimum." This isn't true. You are adding up 2 edges per vertex, where a TSP solution has one ...
• 329
1 vote

### Complexity of solving a higher-order degree polynomial equation? P-problem or NP-problem or neither?

Finding the factorization of a single-variable polynomial with rational coefficients is apparently solvable in poly time, as shown in [1]: [1] Lenstra, A. K.; Lenstra, H. W., Jr.; Lovász, L. Factoring ...
• 10.6k

Only top scored, non community-wiki answers of a minimum length are eligible