**November 10, 2014 at 09:30 - November 14, 2014**
- BCAM & UPV/EHU

**Hubie CHEN, Ikerbasque & UPV/EHU-Universidad del País Vasco / Euskal Herriko Unibertsitatea**

Start date: November 10, 2014

End date: November 14, 2014

Timetable: 9:30 - 11:30

This will be a self-contained introduction to the theory of computability and to computational complexity theory, which will culminate in a thorough discussion of the P versus NP question and the theory of NP-completeness.

Topics to be covered include: finite-state automata, properties and limitations; the Turing machine model, uncomputability, and reductions between problems; fundamental complexity classes such as P and NP, polynomial-time reductions, and examples of NP-hardness proofs.

No background other than "basic mathematical maturity" will be assumed (by this, we understand acquaintance with objects such as sets and functions, and ability to write and read basic proofs).

Approximate plan:

- Introduction and Automata Theory (1.5 days)

- Turing Machines and Computability (1.5 days)

- Computational Complexity (2 days)

***Inscription is required: **So as to inscribe send an e-mail to

roldan@bcamath.org