Computability and Complexity

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

• BCAM-UPVEHU Courses 2014-15