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.

Keine Kommentare: