I came across a theory blog started by Lipton. Here is the link to the blog.
I found a pointer to one of the articles of this blog through Lance Fortnow's weblog.
In the first part of the post, Lipton mentions that the result regarding the closure under complement for space bounded classes was open for a really long time and the fact that people believed that it won't be true was one of the main reasons why it remained open. Lance in his post commented on Lipton's remarks about conventional wisdom regarding NP=P question.
But in any case, thanks to this discussion on the weblog, I got to see a nice informal description of Immerman and Szelepcsenyi's result (which is the second part of Lipton's post). The exposition is useful if you have already seen the result and the proof. It is explained assuming many things and hence it may not be a good read for someone reading the result for the first time.
I would like to stress the fact that the question was first raised for Linear Bounded Acceptors in order to understand closure under complement property of context-sensitive languages.
I do not understand one comment here:
I found a pointer to one of the articles of this blog through Lance Fortnow's weblog.
In the first part of the post, Lipton mentions that the result regarding the closure under complement for space bounded classes was open for a really long time and the fact that people believed that it won't be true was one of the main reasons why it remained open. Lance in his post commented on Lipton's remarks about conventional wisdom regarding NP=P question.
But in any case, thanks to this discussion on the weblog, I got to see a nice informal description of Immerman and Szelepcsenyi's result (which is the second part of Lipton's post). The exposition is useful if you have already seen the result and the proof. It is explained assuming many things and hence it may not be a good read for someone reading the result for the first time.
I would like to stress the fact that the question was first raised for Linear Bounded Acceptors in order to understand closure under complement property of context-sensitive languages.
I do not understand one comment here:
"One interesting note is that for their counting method to work they do not need to get the sets 
exact cardinality. Even a coarse approximation would suffice. This suggests some ideas that might work in other contexts."
Can anyone help me?
exact cardinality. Even a coarse approximation would suffice. This suggests some ideas that might work in other contexts."Can anyone help me?
Comments