tag:blogger.com,1999:blog-3722233.post634513035030909217..comments2024-02-29T15:59:22.700-06:00Comments on Computational Complexity: The two defintions of Chomsky Normal FormLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger3125tag:blogger.com,1999:blog-3722233.post-84564542729416213722015-01-20T02:44:27.485-06:002015-01-20T02:44:27.485-06:00You can use quantification with logarithmic space,...You can use quantification with logarithmic space, if you give the witness string only as one-way input.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-14272618362604645582015-01-19T19:11:17.829-06:002015-01-19T19:11:17.829-06:00LOGCFL as LOG-space reducible to CFL recognition v...LOGCFL as LOG-space reducible to CFL recognition vs languages computable by uniform semi-unbounded fan-in circuits of O(log n) depth. <br /><br />The latter seems preferable mostly because it makes the class seem more natural. Paul Beamehttp://www.cs.washington.edu/homes/faculty/beamenoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-55301720210579318862015-01-19T10:21:39.704-06:002015-01-19T10:21:39.704-06:00Non-deterministic time has several definitions, wh...Non-deterministic time has several definitions, whether we want only one accepting run to be at most $f(n)$, or all possibles runs to be at most $f(n)$. This makes no difference if $f$ is some nicely computable function, but for other $f$ can be a problem.<br /><br />Another definition where one has to be very careful is sublinear space complexity. domhttps://www.blogger.com/profile/05790539025733385232noreply@blogger.com