Log in

No account? Create an account
Computational complexity theory - Arvind Narayanan's journal [entries|archive|friends|userinfo]

Computational complexity theory [May. 6th, 2005|03:29 pm]
Arvind Narayanan

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

[User Picture]From: sunson
2005-05-06 10:46 pm (UTC)
padicha pulla... etho perusu perusa pesutheeha... naala padiyum oi...
(Reply) (Thread)
[User Picture]From: kadambarid
2005-05-06 11:25 pm (UTC)
(Reply) (Parent) (Thread)
From: centerforward
2005-11-18 12:29 pm (UTC)


Even the game of Amazons is PSPACE-complete
(Reply) (Thread)