P vs. NP Problem

At our next meeting on 28th November we will discuss the P vs. NP problem of complexity theory presented by Thomas Zauner. There are several levels of readings.

Level 1
Watch this video explaining the basics about the P vs. NP problem and complexity theory.

Level 2a
Read this article explaining not only the concepts, but also shedding some light on recent developments in research.
http://cacm.acm.org/magazines/2009/9/38904-the-status-of-the-p-versus-np-problem/fulltext

Level 2b
Watch these excellent and well explained lecture video on an introduction complexity. 
https://www.youtube.com/watch?v=moPtwq_cVH8
(For further studies see: https://www.youtube.com/watch?v=eHZifpgyH_4)

Level 3
For further reading consult the always-insightful Stanford encyclopedia of philosophy.
http://plato.stanford.edu/entries/computational-complexity/

Gödel’s incompleteness theorem

Responsible: Moritz Kriegleder

To read I have 3 levels of literature increasing in depth:

Level 1 Tall:

http://www.nytimes.com/2005/05/01/books/review/incompleteness-waiting-for-godel.html?_r=1

As a short introduction and a little historical background this will be the starting point of our discussion.
We all have a lot to do, so if you’ve read and thought about this, we can have a good chat.

Level 2 Grande:

http://plato.stanford.edu/entries/goedel-incompleteness/

As always I recommend the stanford library, mathematically precise but still a lot historical and philosophical context.
I will mainly talk about this text and if you want to, you can also have a look.

Level 3 Venti:

http://www.logicmatters.net/resources/pdfs/gwt/GWT2f.pdf

Goedel without tears is a really nice starting point for thorough understanding that helps people that dont know all set theorie
and theoretical informatics to tackle goedels points in a complete mathematical way. I started the book in summer and
really liked it but didnt have the time to finish it.

Level Goedel:
If these 200 pages are still not enough for you or you’re just interested in the OG paper,
here is the modern translation of the original text: http://www.research.ibm.com/people/h/hirzel/papers/canon00-goedel.pdf