Posts mit dem Label survey werden angezeigt. Alle Posts anzeigen
Posts mit dem Label survey werden angezeigt. Alle Posts anzeigen

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.