# Tag Info

## Hot answers tagged complexity-classes

101 votes
Accepted

### Is Norbert Blum's 2017 proof that $P \ne NP$ correct?

As noted here before, Tardos' example clearly refutes the proof; it gives a monotone function, which agrees with CLIQUE on T0 and T1, but which lies in P. This would not be possible if the proof were ...
• 1,026
94 votes

### Is Norbert Blum's 2017 proof that $P \ne NP$ correct?

I am familiar with Alexander Razborov whose previous work is extremely crucial and serves as a foundation for Blum's proof. I had the good luck of meeting him today and wasted no time in asking for ...
• 711
40 votes

### Is Norbert Blum's 2017 proof that $P \ne NP$ correct?

This is posted as community answer because (a) it's not my own words, but a citation from Luca Trevisan on a social media platform or from other people with no CSTheory.SE account; and (b) anyone ...
35 votes

### Is Norbert Blum's 2017 proof that $P \ne NP$ correct?

The correctness of the claimed proof is being discussed at Luca Trevisan's blog: https://lucatrevisan.wordpress.com/2017/08/15/on-norbert-blums-claimed-proof-that-p-does-not-equal-np/ In particular "...
• 1,047
30 votes

### Problems with big open complexity gaps

The Knot Equivalence Problem. Given two knots drawn in the plane, are they topologically the same? This problem is known to be decidable, and there do not seem to be any computational complexity ...
• 23.9k
29 votes
Accepted

### If P = NP were true, would quantum computers be useful?

The paper "BQP and the Polynomial Hierarchy" by Scott Aaronson directly addresses your question. If P=NP, then PH would collapse. If furthermore BQP were in PH, then no quantum speed-up would be ...
• 5,436
28 votes

### What are the consequences of $\mathsf{L}^2 \subseteq \mathsf{P}$?

• 2,281
28 votes
Accepted

### What are the consequences of $\mathsf{L}^2 \subseteq \mathsf{P}$?

The following is an obvious consequence: $\mathsf{L}^{1+\epsilon} \subseteq \mathsf{P}$ would imply $\mathsf{L} \subsetneq \mathsf{P}$ and therefore $\mathsf{L} \neq \mathsf{P}$. By the space ...
• 556
26 votes

### Is there a natural problem in quasi-polynomial time, but not in polynomial time?

There has, in fact, been quite a lot of recent works on proving quasi-polynomial running time lower bound for computational problems, mostly based on the exponential time hypothesis. Here are some ...
26 votes
Accepted

### Has parameterized complexity led to better algorithms?

There are several examples of problems where a parameterized algorithm performs well in practice. Let me mention two such problems. In the $k$-Path problem where we are looking for a simple path of ...
24 votes

### Problems with big open complexity gaps

Here's a version of the minimum circuit size problem (MCSP): given the $2^n$ bit truth table of a Boolean function, does it have a circuit of size at most $2^{n/2}$? Known to be not in $AC0$. ...
• 26.7k
24 votes

### Problems with big open complexity gaps

The complexity of computing a bit (specified in binary) of an irrational algebraic number (such as $\sqrt{2}$) has the best known upper bound of $\mathsf{P^{{{PP}^{PP}}^{PP}}}$ via a reduction to the ...
• 2,299
24 votes

### Is Norbert Blum's 2017 proof that $P \ne NP$ correct?

Gustav Nordh commented on by Theorem 5 (page 29). Specifically, the function $$(x\lor y) \land (\lnot x \lor y) \land (x \lor \lnot y)$$ computes the function which is $1$ only if $x$ and $y$ are ...
• 349
24 votes
Accepted

### How "hard" is it to maximize a polynomial function subject to linear constraints?

Your problem is NP-hard, even for polynomials of degree 2. The crucial reference is Theodore Motzkin and Ernst Strauss (1965) "Maxima for graphs and a new proof of a theorem of Turan" ...
• 5,742
23 votes
Accepted

### Problems in BQP but conjectured to be outside P

To have a list of such problems, you can look at the list of superpolynomial speed improvement at the quantum algorithm zoo (QAZ). The list below is based on this (see QAZ for precise definitions and ...
23 votes

### Is there a natural problem in quasi-polynomial time, but not in polynomial time?

Megiddo and Vishkin proved that Minimum dominating set in tournaments is in $QP$. They showed that tournament dominating set has P-time algorithm iff SAT has subexponential time algorithm. Therefore, ...
22 votes

### Problems with big open complexity gaps

Another natural topological problem, similar in spirit to Peter Shor's answer, is embeddability of 2-dimensional abstract simplicial complexes in $\mathbb{R}^3$. In general it's natural to ask when ...
• 18.1k
20 votes
Accepted

Just an extended comment to better explain ARi's comment (I was writing it while I saw it). It is sufficient to use a "large gap" approach similar to the one used in Lardner's theorem; for example: $... • 22.4k 20 votes ### Tardos Function Counterexample to Blum's$P\neq NP$Claim so these remarks imply that the Tardos function$f$is the same as CLIQUE. Short answer - NO. It is only a *monotone* "clique-like": accepts all$k$-cliques, and rejects all complete$(k-1)$-... • 6,655 19 votes ### To which complexity class does this language belong? (as pointed out by Robin the problem is in DP...) ...and it is also DP-complete. In fact, Jörg Rothe has shown that this even holds for fixed k=4: Jörg Rothe: Exact complexity of Exact-Four-... • 1,387 17 votes ### Problems with big open complexity gaps Multicounter automata (MCAs) are finite automata equipped with counters that can be incremented and decremented within one step but only take integers >=0 as numbers. Unlike Minsky machines (aka ... • 1,387 17 votes Accepted ### Potentially equal complexity classes without known contradictory relativizations I think the biggest such example at present is$BQP $(quantum polybomial time) vs$PH $(the polynomial time hierarchy). Significant effort has been put into separating them relative to an oracle, ... • 26.7k 17 votes ### Is Norbert Blum's 2017 proof that$P \ne NP$correct? Could one use list decoding of Reed-Solomon codes to show Andreev's POLY function is in P, similar to the way Sivakumar did in his membership comparable paper? Or is the POLY function known to be NP-... • 8,546 16 votes Accepted ### Natural candidates for NP-E and E-NP TQBF (True Quantified Boolean Formulas) is in E and won't be in NP unless NP = PSPACE. A language in NP-E is trickier. Such a language would also be in NP-NTIME(n) and we don't have great examples of ... • 8,546 15 votes Accepted ### What is an equivalent definition of mP/poly in terms of a Turing machine? There is a notion of a monotone non-deterministic and, more generally, alternating Turing machine in the paper Monotone Complexity by Grigni and Sipser. Since polynomial time is the same as ... • 4,531 15 votes ### Is Norbert Blum's 2017 proof that$P \ne NP$correct? He has updated his arXiv to say his proof is incorrect: The proof is wrong. I shall elaborate precisely what the mistake is. For doing this, I need some time. I shall put the explanation on my ... • 421 14 votes Accepted ### To which complexity class does this language belong? It is contained in DP: Difference Polynomial-Time, which is also BH$_2$, the second level of the Boolean hierarchy. This class is itself contained in$\Delta^\textrm{P}$, but that is believed to be a ... • 13.4k 14 votes Accepted ###$\mathsf{EXP}$vs$\oplus\mathsf{EXP}$In terms of complexity reasons (rather than complete problems): The Hartmanis-Immerman-Sewelson Theorem should also work in this context, namely:$\mathsf{EXP} \neq \oplus \mathsf{EXP}$iff there is a ... • 36.3k 14 votes ### What are the relationships between those hypotheses in Fine-Grained Complexity Theory? This is a recent paper introducing Nondeterministic Strong Exponential Time Hypothesis (NSETH), which is an extension of SETH. NSETH: For every$\epsilon >0$, there is a$k$such that$k$-DNF-TAUT ... • 141 13 votes ### Complexity of max problem It depends how the polytope is represented. In the V-polytope presentation (i.e.$P\$ is given in terms of its vertices), the problem is trivial, as Tim mentioned in the comments. In the H-polytope ...
• 18.1k

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