P = BPP?

Don Knuth's musings are great, always describing some amazing thing unknown to me before.

Knuth's Algorithm X finds all solutions to the exact cover problem. What is so magical about it is the technique he proposed to efficiently implement it: Dancing Links.

I think we must include Schieber-Vishkin's, which answers lowest common ancestor queries in constant time, preprocessing the forest in linear time. I like Knuth's exposition in Volume 4 Fascicle 1, ...

See exercise 9 of section 6.4 of The Art of Computer Programming. Any irrational $A$ would work, because $\{kA\}$ breaks up a largest gap of $\{A\}, \{2A\}, \ldots, \{(k-1)A\}$ (I use the notation $\{... View answer 13 votes A good example is Barrington's theorem: If a boolean function$f$is computable by a circuit of depth$d$, then$f$is computable by a branching program of width 5 and length$4^d$. The ... View answer 12 votes We cannot forget Binary Decision Diagrams, a family of data structures that have become the method for representing boolean functions. I think the key insight is the dual nature of being a data ... View answer 9 votes Actually this is might be good question but it is badly formulated in its current form. The well-known algorithms for generating random derangements have linear expected time, but maybe it's an open ... View answer 9 votes (This was meant as a comment, but went long). Very interesting question. If you are willing to think about other complexity measures besides Kolmogorov's, then there are some answers in Learning ... View answer 8 votes The application you mention is called "proof of useful work" in the literature, see for instance this article. You can use a fully homomorphic encryption scheme (where the plaintext is the CNF ... View answer Accepted answer 7 votes I've found that this problem is NP-hard, even restricted to trees. The reference is Graham and Robinson, "Isomorphic factorizations IX: even trees", but I couldn't get it. View answer 7 votes I think the most used algorithm is Parity Check (or maybe CRC or some kind of error-correcting code), because they appear in every RAM access. View answer 7 votes Knuth-Bendix algorithm and the analogous Buchberger's algorithm. View answer 6 votes How much damage could be caused by a peer reviewer having a bad day? Hilarious fictional reviews of famous old CS papers. View answer 6 votes It is well-known the result of Coppersmith and Winograd that$O(n^{\omega})$-time cannot be realized by any single algorithm. But I've read that they restricted to algorithms based on Strassen-like ... View answer 6 votes I think that LR parsers are beautiful. A language is deterministic context-free if and only if there exists a LR(1) grammar for it. View answer 5 votes Peter Shor's answer is really good, but there is another way to answer this: proving that treewidth is upper bounded by two times the amplitude (the vertex version). Since we know that 3-regular ... View answer 3 votes The winner of the 2007 Aaronson/Gasarch Complexity Theme Song Contest is amazing! Download the mp3 and its lyrics. View answer 3 votes Cubic Montone Planar 1-in-3 SAT: 1-in-3 SAT without negated variables and where each variable is in exactly 3 clauses, and the incidence graph (the bipartite graph where the variables and the clauses ... View answer 2 votes Although mikero proved that your problem is hard, there is a fast general algorithm that gives reasonably good solutions to this kind of problem (where you want an ordering of a set of "objects" such ... View answer Accepted answer 2 votes See the answers of this question. Your case is a lot easier, just choose$k$of the$m$columns and then you have$n (n-1)\ldots (n-k+1)$ways to put the$k$rooks. So the coefficient of$x^k$is$\...

EXACT COVER BY 3-SETS to SUBSET SUM EXACT COVER BY 3-SETS: given $U=\{1,2,\ldots,3m\}$ and $S_1,\ldots,S_n$ 3-subsets of $U$, are there $m$ disjoint sets that cover $U$? SUBSET SUM: given integers \$...