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.

Level 2b
Watch these excellent and well explained lecture video on an introduction complexity. 
(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.

Gödel’s incompleteness theorem

Responsible: Moritz Kriegleder

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

Level 1 Tall:


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:


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:


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