2 Matching Annotations
  1. Mar 2019
    1. Special Complexity Zoo Exhibit: Classes of Quantum States and Probability Distributions 24 classes and counting! A whole new phylum of the Complexity kingdom has recently been identified. This phylum consists of classes, not of problems or languages, but of quantum states and probability distributions. Well, actually, infinite families of states and distributions, one for each number of bits n. Admittedly, computer scientists have been talking about the complexity of sampling from probability distributions for years, but they haven't tended to organize those distributions into classes designated by inscrutable sequences of capital letters. This needs to change.
    1. I hope that non-theorists, even if they don't understand everything, will at least find some amusement in the many exotic beasts that complexity theory has uncovered.