Arvind Narayanan (arvindn) wrote,
Arvind Narayanan

Computational complexity theory

5 cool facts I learnt in my Theory of Computation class this semester:

* If E is not contained in P/poly then P = BPP (where E = DTIME (2^O(n)))
* The game of Go is PSPACE-complete
* We don't know whether or not BPP has complete problems
* Multiplication is in NC1 (a.k.a Wallace tree multiplier)
* Any randomized complexity class is contained in the corresponding nonuniform class
Tags: work
  • Post a new comment


    Comments allowed for friends only

    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded