Search results

...ending me a great deal of relevant information; Bill Gasarch for preparing a summary of communication complexity classes; [[Lawrence Ip]] for suggesting [[Category:Computational Complexity]]

''This page is a pronunciation guide for the [[Complexity Zoo]] which was originally created ...of rarer complexity classes. Usually the safest bet is just to spell out a whole acronym; even when vowels are present, this is easier than wrapping o

I created the Complexity Zoo with three audiences in mind. ...that, before hoisting one more brick onto the vast edifice of complexity, I'd do well to take stock of what was already known. Some theorists seem abl

...d <i>probability distributions</i>. Well, actually, infinite <i>families</i> of states and distributions, one for each number of bits n. ...analogous project for quantum states; indeed, he puts the classes below in a special exhibit to avoid the appearance of favoritism toward his own classe

<i>"Now you too can speak Theorese!"</i> On this page I've collected terms that appear (or don't appear) throughout the Complexity

[[Category:Computational Complexity]] ...wever, all additions are welcome, and it is hoped that this will grow into a comprehensive collection.''

...for the terrifying and complex beasts lurking in the main zoo. It will be a gentler source of information about major complexity classes, problems, and ...h to apply to whatever computer you may want to use, be it a wristwatch or a supercomputing cluster. The model that we shall use to do so is that of the

===== A ===== <i>Proceedings of ACM STOC'2002</i>, pp. 635-642, 2002.