tag:blogger.com,1999:blog-3722233.post111931245078335058..comments2024-03-18T22:18:20.292-05:00Comments on Computational Complexity: Favorite Theorems: The Polynomial-Time HierarchyLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger4125tag:blogger.com,1999:blog-3722233.post-19654450688261720222024-03-17T13:35:25.954-05:002024-03-17T13:35:25.954-05:00As practical (i.e. non-theoretic) programmer that ...As practical (i.e. non-theoretic) programmer that needed to learn about PSPACE-to-NFA_universality algorithm, this paper was very bizzare<br /><br />"okay, so this paper actually explaines EXPSPACE-to-SqNFA_uni, but I can deal with that<br />waaait, why is there still half a paper left? it's... polynomial heirarchy? did authors steal it to add to the end, lol?"<br /><br />having learned about PH only from wikipedia... I did not know this paper was a classic of this scale<br /><br />(also PSPACE-to-NFA_uni construction derived from this paper and appearing in several textbooks can be shortened and optimized at least in half...)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1119926616168462052005-06-27T21:43:00.000-05:002005-06-27T21:43:00.000-05:00Marcus Schaefer and Chris Umans wrote a two-part s...Marcus Schaefer and Chris Umans wrote a two-part survey on completeness in the polynomial-time hierarchy for SIGACT News. (Most of the problems are in the second level, but some are in the third.)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1119915502625511042005-06-27T18:38:00.000-05:002005-06-27T18:38:00.000-05:00I seem to recall that the SIGACT News complexity t...I seem to recall that the SIGACT News complexity theory column was going to run a column on problems complete for "high" levels of the polynomial hierarchy. (Here "high" means >2). Did that ever happen?<BR/><BR/>-David MolnarAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1119314414848808812005-06-20T19:40:00.000-05:002005-06-20T19:40:00.000-05:00Lance,I think you recently told that this problem ...Lance,<BR/>I think you recently told that this problem is not "natural":)Anonymousnoreply@blogger.com