A message from our CEO about the future of Stack Overflow and Stack Exchange. Read now.

# Tag Info

97

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 correct, since the proof applies to this case too. However, can we pinpoint the mistake? Here is, from a post on the lipton's blog, what seems to be the place ...

95

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 his opinion on this whole matter, on whether he had even seen the proof or not and what are his thoughts about it if he did. To my surprise, he replied that he ...

41

Turing-machines and $\lambda$-calculus are equivalent only w.r.t. the functions $\mathbb{N} \rightarrow \mathbb{N}$ they can define. From the point of view of computational complexity they seem to behave differently. The main reason people use Turing machines and not $\lambda$-calculus to reason about complexity is that using $\lambda$-calculus naively ...

41

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 should feel free to update this with updated, relevant information. Quoting Luca Trevisan from a public Facebook post (08/14/2017), replying to a question about ...

36

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 "anon" posted the following relevant comment: "Tardos observed that Razborov’s and Alon-Boppana’s arguments carry over to a function which is computed by a ...

33

A flip answer is that this isn't the first thing about complexity theory that I'd try to explain to a layperson! To even appreciate the idea of nonuniformity, and how it differs from nondeterminism, you need to be further down in the weeds with the definitions of complexity classes than many people are willing to get. Having said that, one perspective that ...

31

Yes. In fact, by the McCreight-Meyer Union Theorem (Theorem 5.5 of McCreight and Meyer, 1969, free version here) a result of that I believe is due to Manuel Blum, there is a single function $f$ such that $\mathsf{P} = \mathsf{DTIME}(f(n))$. This function is necessarily superpolynomial, but "just barely." The theorem applies more generally to any Blum ...

30

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 possible in that case. On the other hand, Aaronson gives evidence for a problem with quantum speedup outside PH, thus such a speed-up would survive a collapse of PH.

29

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 obstructions to its being in P. The best upper bound currently known on its time complexity seems to be a tower of $2$s of height $c^n$, where $c = 10^{10^{6}}$, ...

28

Mulmuley's result (from Mulmuley's webpage without paywall) that, in the PRAM model without bit operations, "$\mathsf{P} \neq \mathsf{NC}$". (In the usual boolean model where $\mathsf{L}$ lives, $\mathsf{L} \subseteq \mathsf{NC}$.) This model is strong enough that the result implies any $\mathsf{L}$ algorithm for a $\mathsf{P}$-complete problem would have to ...

28

If $\mathsf{NP} = \mathsf{PSPACE}$, this would imply: $\mathsf{P^{\#P}} = \mathsf{NP}$That is, counting the solutions to a problem in $\mathsf{NP}$ would be polytime reducible to finding a single solution; $\mathsf{PP} = \mathsf{NP}$That is, polynomial-time randomized algorithms with success probability arbitrarily close to 1/2 is polynomial-time reducible ...

28

Here is a "smoothness" argument that I heard recently in defense of the claim that non-uniform models of computation should be more powerful than we suspect. On one hand, we know from the time hierarchy theorem that there are functions computable in time $O(2^{2n})$ that are not computable in time $O(2^{n})$, for example. On the other hand, by Lupanov's ...

27

The class ${\cal C}$ you are proposing is probably not $NP$. (If ${\cal C} = NP$, then every $NP$ language would have linear-size witnesses, which would imply that every $NP \subseteq TIME[2^{O(n)}]$ and $NP \neq EXP$, among other things). It is very natural to consider such classes; they arise in several settings. In this paper, Rahul Santhanam (...

27


25

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 results for problems that I consider quite natural (all results below are conditional on ETH): Aaronson, Impagliazzo and Moshkovitz [1] show a quasi-polynomial ...

25

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 both $1$, hence it is monotone. The expression above for the function represents a "standard network" $\beta$ (where the only negations are to a literal) whose ...

24

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$. Contained in $NP$. Generally believed to be $NP$-hard, but this is open. I believe it's not even known to be $AC0[2]$-hard. Indeed, recent work with Cody Murray (to ...

24

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 problem $\mathsf{BitSLP}$ which known to have this upper bound [ABD14]. On the other hand we do not even know if this problem is harder than computing the ...

23

Wigderson proved that $NL/poly \subseteq \oplus L/poly$. By standard arguments, $L = \oplus L$ would imply $L/poly = NL/poly$. (Take a machine $M$ in $NL/poly$. It has an equivalent machine $M'$ in $\oplus L/poly$. Take the $\oplus L$ language of instance-advice pairs $S = \{(x,a)~|~M'(x,a)~\textrm{accepts}\}$. If this language is in $L$, then by ...

23

You need to understand that $\mathsf{CSP}$ problems have a structure that generic $\mathbf{SAT}$ problems do not have. I will give you a simple example. Let $\Gamma=\{\{(0,0),(1,1)\},\{(0,1),(1,0)\}\}$. This language is such that you can only express equality and inequality between two variables. Clearly any such set of constraints is ...

23

One point which has been implicitly but not explicitly mentioned yet is that we would get $\mathsf{NP} = \mathsf{coNP}$. Although this is equivalent to $\mathsf{PH}$ collapsing to $\mathsf{NP}$, it follows directly from the fact that $\mathsf{PSPACE}$ is closed under complement, which is trivial to prove. I think $\mathsf{NP} = \mathsf{coNP}$ is worth ...

22

Supposedly the reference "NP-complete problems on a 3-connected cubic planar graph and their applications" by Uehara (a paper I haven't actually seen) proves that independent set is NP-complete even for triangle-free planar graphs. But by Grötzsch's theorem they are always 3-colorable, and testing for smaller numbers of colors than 3 is easy in any graph, so ...

22

I recommend Jenga! Assuming you have two perfectly logical, sober, and dextrous players, Jenga is a perfect-information two-player game, just like Checkers or Go. Suppose the game starts with a stack of $3N$ bricks, with 3 bricks in each level. For most of the game, each player has $\Theta(N)$ choices at each turn for the next move, and in the absence of ...

22

In some technical sense you are asking whether $P = NP \cap coNP$. Suppose that $L \in NP \cap coNP$, thus there exists poly-time $F$ and $G$ so that $x \in L$ iff $\exists y: F(x,y)$ and $x \not\in L$ iff $\exists y: G(x,y)$. This can be recast as a minmax characterization by $f_x(y) = 1$ if $F(x,y)$ and $f_x(y) = 0$ otherwise; $g_x(y) = 0$ if $G(x,y)$ ...

22

$DTIME(n^{polylogn})$ is known as $QP$ (quasi-polynomial). It is widely believed that $NP\not \subset QP$, although it is a stronger statement than $P\neq NP$. Some common conjectures, such as the Exponential Time Hypothesis imply $NP\not \subset QP$.

22

3-SAT may be one such problem. Currently the best upper bound for Unique 3-SAT is exponentially faster than for general 3-SAT. (The speedup is exponential, although the reduction in the exponent is tiny.) The record-holder for the unique case is this paper by Timon Hertli. Hertli's algorithm builds upon the important PPSZ algorithm of Paturi, Pudlák, ...

22

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 can we effectively/efficiently decide that an abstract $k$-dimensional simplicial complex can be embedded in $\mathbb{R}^d$. For $k=1$ and $d=2$ this is the graph ...

22

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 references. This is another way to say I don’t even pretend to understand many of the problems of this list!) Algebraic and Number Theoretic Problems If I’m ...

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