Session:Wondrous mathematics: A gentle introduction to P vs. NP, the biggest open question in computer science

From 36C3 Wiki
Description Very roughly, P is the class of efficiently solvable problems and NP is the class of non-efficiently solvable problems. A basic fact of life is P ≠ NP. However, for the last fifty years, this observation has stubbornly resisted every attempt of a proof. The talk will carefully explain ... (see long description)
Website(s)
Type Talk
Kids session No
Keyword(s) science, coding
Tags mathmatics
Processing assembly Assembly:Curry Club Augsburg
Person organizing Iblech
Language en - English
en - English
Other sessions... ... further results

(Click here to refresh this page.)

Starts at 2019/12/27 21:50
Ends at 2019/12/27 22:50
Duration 60 minutes
Location Room:Lecture room M1

The talk will carefully explain:

  • what the precise statement of the conjecture P ≠ NP is
  • how the world would look like if P = NP
  • whether it might be that it's provable that the conjecture is unprovable (that the conjecture exceeds the boundaries of logic)
  • what's known about hypothetical proofs of P ≠ NP

This talk requires no mathematical prerequisites. Indeed, people who took classes on computability theory in university will be bored to hell and should only attend if they plan to support the session by offering interesting remarks. :-) To enjoy and follow the talk, you should know that we use algorithms to solve computational problems and that some are more efficient than others. You'll be extra prepared if at some point in your life you've implemented some algorithms. That said, you will only enjoy the talk if you enjoy mathematical thinking and a certain amount of mathematical precision. This is not a light-and-fun talk, to the small extent that it's fun it's only thanks to the interesting theoretical relationships discussed in the talk.

Slides

Some details (in German)

Survey paper by Scott Aaronson (very much recommended)

Thanks are due to Anna Rubeck who prepared an earlier version of this talk and who inspired me to give this talk.

Archived page - Impressum/Datenschutz