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 ...
Gamow's user avatar
  • 5,772
19 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 ...
usul's user avatar
  • 7,615
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: ...
Marzio De Biasi's user avatar
15 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 ...
domotorp's user avatar
  • 14k
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}: \...
Barış Aydınlıoğlu's user avatar
13 votes
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$) ...
Emil Jeřábek's user avatar
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. ...
Charles's user avatar
  • 1,735
12 votes

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-...
Avi Tal's user avatar
  • 1,606
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. ...
Chao Xu's user avatar
  • 4,439
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'...
Ryan Williams's user avatar
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, ...
cody's user avatar
  • 13.9k
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 ...
Tayfun Pay's user avatar
  • 2,598
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$.
Bjørn Kjos-Hanssen's user avatar
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 ...
Michael Lampis's user avatar
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 ...
Lem's user avatar
  • 51
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 ...
Joshua Grochow's user avatar
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$ ...
Andras Farago's user avatar
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-...
Bjørn Kjos-Hanssen's user avatar
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$.
Yuval Filmus's user avatar
  • 14.5k
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 ...
Mohammad Al-Turkistany's user avatar
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 ...
Geoffrey Irving's user avatar
2 votes
Accepted

Unambiguous SAT and sparse languages

It puts NP into P/poly, and therefore collapses PH to its second level. By basically the same as the usual proof that BPP is in P/poly, there is polynomial advice that provides good random bits for ...
Joshua Grochow's user avatar
2 votes

Formulating P vs NP without Turing machines

In Descriptive Complexity, consider the logical language consisting of two sorts: unary numbers $x$ and binary string $Y$, and $\{0,1,+,*, \leq, =\}$ on unary numbers (commutative discrete ordered ...
Kaveh's user avatar
  • 21.6k
2 votes

Why if non determinism adds no power at all to DFAs or to Turing machines, why is it that most people beleieve P != NP

The equivalence you're talking about is a very coarse one. The DTM $A$ corresponding to an NTM $B$ in the obvious way will accept the same language as $B$, but it will do so vastly more slowly. Since ...
Noah Schweber's user avatar
2 votes
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 ...
Ilk's user avatar
  • 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 ...
NaturalLogZ's user avatar
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 ...
Neal Young's user avatar
  • 10.6k

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