Here's a simplification of Ryan's answer. Suppose that $\Lambda \in NE \setminus E$. Define the language $L = \{x : |x| \in \Lambda\}$. The assumption $\Lambda \in NE \setminus E$ translates to $L \in ... View answer 30 votes Let$f\colon \{0,1\}^n \to \{0,1\}$be a boolean function. If it has a polynomial representation$P$then it has a multilinear polynomial representation$Q$of degree$\deg Q \leq \deg P$: just ... View answer Accepted answer 29 votes You should check the Hajós calculus. Hajós showed that every graph with chromatic number at least$k$has a subgraph which has a "reason" for requiring$k$colors. The reason in question is a proof ... View answer 20 votes Russell Impagliazzo's proof of Ladner's theorem furnishes an example for 3. For completeness' sake, below I copy the definition of the algorithmic task$X$and sketch the proof that it is on "both ... View answer 19 votes The most natural restriction on the proof DAG is that it be a tree – that is, any "lemma" (intermediate conclusion) is not used more than once. This property is called being "tree-like". General ... View answer Accepted answer 19 votes No. Consider the following function on$\{0,1\}^n$: $$f(x) = x_0 \land \cdots \land x_{n-\sqrt{n}-1} \land (x_{n-\sqrt{n}} \oplus \cdots \oplus x_{n-1}).$$ Clearly this function is hard for AC0. On ... View answer Accepted answer 19 votes In the first part, we show an exponential algorithm for deciding circularity. In the second part, we show that this the problem is coNP-hard. In the third part, we show that every circular language is ... View answer Accepted answer 18 votes I believe that the notation AC first appears in Cook's "A Taxonomy of Problems with Fast Parallel Algorithms" from 1985. On page 11 (page 12 of the journal) we read: To state a more general form of ... View answer Accepted answer 16 votes The number field sieve has never been analyzed rigorously. The complexity that you quote is merely heuristic. The only subexponential algorithm which has been analyzed rigorously is Dixon's ... View answer Accepted answer 16 votes According to Garey and Johnson (p. 174), REGULAR EXPRESSION NON-UNIVERSALITY is PSPACE-complete. This is the problem of deciding whether a regular expression over$\{0,1\}$does not generate all ... View answer Accepted answer 14 votes There are two loanable copies at The National Library of Israel. Here is a scanned copy. View answer Accepted answer 14 votes No, the bombe was very specific. It consisted of a bunch of enigma machines hooked together. It was very limited in its use. A more interesting question is whether the Colossus computer, also used in ... View answer Accepted answer 14 votes Your problem is equivalent to maximum matching. In an optimal coloring, each color class is connected. Choosing one edge from each color class, we get a matching. This shows that the maximum matching ... View answer 14 votes Assume for simplicity that$n = 2^m$. Use the linear time selection algorithm to find the elements at positions$2^{m-1},2^{m-2},2^{m-3},\ldots,1$; this takes linear time. Given$k$, find$t$such ... View answer Accepted answer 14 votes Your problem is known in the learning literature as "learning monotone functions using membership queries". A class of monotone functions for which one can identify all minterms is known as "... View answer Accepted answer 13 votes Any problem in ZPP is computable (in fact, it is in the intersection of NP and coNP). Given any ZPP machine, run it in parallel with a deterministic machine that solves the same problem. This affects ... View answer Accepted answer 13 votes Johnson graphs are actually easy to recognize. In particular, you can recognize whether an input graph is a Johnson graph in polynomial time, and you can construct an isomorphism between two ... View answer 13 votes Here is what Scott Aaronson has to say on the subject: What makes this interesting is that block-sensitivity is known to be polynomially related to a huge number of other interesting complexity ... View answer 13 votes De, Kurur, Saha and Saptharishi gave a modular version of Fürer's integer multiplication algorithm in their paper Fast integer multiplication using modular arithmetic, in which the p-adic numbers ... View answer Accepted answer 13 votes One way is described in Berkowitz, On computing the determinant in small parallel time using a small number of processors (see also Soltys, Berkowitz's algorithm and clow sequences). Another way is ... View answer 13 votes Not exactly what you asked for, but a situation "in the wild" in which a log factor appears in the denominator is the paper "Pebbles and Branching Programs for Tree Evaluation" by Stephen Cook, Pierre ... View answer 13 votes In the oracle world, it is easy to give examples where randomness gives us much more power. Consider, for example, the problem of finding a zero of a balanced Boolean function. A randomized algorithm ... View answer 13 votes Classical work of Coppersmith shows that for some$\alpha > 0$, one can multiply an$n \times n^\alpha$matrix with an$n^\alpha \times n$matrix in$\tilde{O}(n^2)$arithmetic operations. This is ... View answer 13 votes The solution of Annihilation Games (Fraenkel and Yesha) has complexity$O(n^6)$. View answer 13 votes It depends on your definition of "Computer Science". Take the example below - does it count? A coding of the integers is a uniquely decodable binary code of$\mathbb{N}$. If the length of the ... View answer 13 votes Chomsky normal form A CFG is in CNF (Chomsky normal form) if the only productions are of the form$A \rightarrow a$and$A \rightarrow BC$; a grammar can be brought to CNF with only quadratic blowup.... View answer 13 votes Edit: This solves an earlier version, in which we have to decide whether there is an equality of the form$\alpha_{i_1} \cdots \alpha_{i_K} = \beta_{j_1} \cdots \beta_{j_{K'}}$. The new version ... View answer 12 votes Consider the$n$vectors$e_1,\ldots,e_n$of weight$1$, and the zero vector$e_0$. The Hamming distance between$e_0$to any$e_i$is$1$. Let$\varphi$be a map into a Hamming cube of dimension$m$, ... View answer 12 votes The best known example is probably checkers (also known as draughts), which has been solved recently in 2007 (the game is a draw). Other examples are listed in the Wikipedia page on solved games; ... View answer 12 votes There is some sort of explanation in the book Algebraic Complexity Theory by Bürgisser, Clausen and Shokrollahi (p. 11-12). The idea is to start with two bases$A_0,A_1,A_2,A_3$and$B_0,B_1,B_2,B_3\$ ...