Timeline for Survey on Structural Complexity
Current License: CC BY-SA 3.0
9 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 12, 2011 at 7:33 | comment | added | Suresh Venkat | A book that needs to be updated, but was perfect at the time, was Structural Complexity by Balcazar, Diaz and Gabarro: books.google.com/books/about/… | |
| Sep 8, 2011 at 2:27 | comment | added | Kaveh | ps: I am not sure if the results you want to know about are part of structural complexity theory: en.wikipedia.org/wiki/Structural_complexity_theory | |
| Sep 8, 2011 at 2:26 | comment | added | Kaveh | related question on cstheory: cstheory.stackexchange.com/questions/811/… | |
| Sep 7, 2011 at 16:10 | answer | added | András Salamon | timeline score: 5 | |
| Sep 7, 2011 at 15:38 | comment | added | structural complexity | (I'm certain said authors of textbooks are experts in the arena; the problem is I can;t find any survey type exposition of the topics.) | |
| Sep 7, 2011 at 15:37 | comment | added | structural complexity | Intro level textbooks cover thigns like P, NP, BPP, L, NL, RL, coNL, space complexit hierarcy, time hiearchy. However, there's alot of work on Interactive Proofs / Zero knowledge proof of knowedge that I don't see in these books. | |
| Sep 7, 2011 at 15:35 | comment | added | David White | Doesn't Sipser's book "Introduction to the Theory of Computation" have some nice tables breaking down what's known? I don't have my copy on me, but I remember him devoting lots of time to P, NP, and other classes for both time complexity and space complexity. Admittedly, that might be a bit out of date and probably won't contain all the fine divisions, but it seems a good place to start. | |
| Sep 7, 2011 at 15:32 | history | edited | David White |
edited tags
|
|
| Sep 7, 2011 at 15:22 | history | asked | structural complexity | CC BY-SA 3.0 |