Montag, 19. Juli 2010

Complexity Theory related surveys

Some complexity related survey-ish papers:
A CACM article from September 2009 titled "The status of the P versus NP problem" available here.

Mentioned in the above survey, two more interesting papers:
  • an article by Scott Aaronson on the independence of the P vs. NP question
  • a paper by Impagliazzo giving a personal view on the average case complexity
I did not have enough time to read more of the cited works in the CACM article, but I'll add more as I have time to read it.

Dienstag, 6. Juli 2010

Coalgebraic Logic

Due to recent needs, I looked up some stuff on coalgebraic logic, a generalization of modal logics. If you're unfimiliar with the notion of coalgebras, read the good 'tutorial on coalgebras and coinduction' by Jacobs and Rutten.
I keep extending this post to contain a small collection of useful reading material, staring with this list:

For modal logics per se, have a look at the handbook of modal logics.