The theory of computational complexity provides tools for analysing the minimal amount of computational resources that are needed for algorithmically solving a problem. The classical resources that are studied are time and memory usage, but more recent developments have shown that several other computational resources are equally relevant, such as the amount of randomness needed by the algorithm, or the depth of the circuit that implements the algorithm as a measure of its parallelism. Besides introducing the basics of the theory, in this course we will spend some time discussing the relevance of the famous P vs. NP problem and its relatives to computer science and technology, but also its relevance to other areas of science.
Syllabus: Models of computation and computational resources: time, space, randomness, circuit-depth and circuit-size. Basic complexity classes, reductions and completeness, P vs. NP problem. Randomness as a resource and tool, probabilistic proof systems. Complexity of sampling and combinatorial counting problems. Advanced topics: circuit lower bounds, derandomization, PCP-theorem and inapproximability.
Professorat
Responsable
Albert Atserias Peri (
)
Altres
Antoni Lozano Boixadors (
)
Hores setmanals
Teoria
2
Problemes
2
Laboratori
0
Aprenentatge dirigit
0
Aprenentatge autònom
4
Competències
Competències Tècniques de cada especialitat
Computació avançada
CEE3.1 - Capacitat per a identificar barreres computacionals i analitzar la complexitat de problemes computacionals en diversos àmbits de la ciència i la tecnologia; així com per representar problemes d'alta complexitat en estructures matemàtiques que puguin ser tractades eficientment amb esquemes algorítmics.
CEE3.3 - Capacitat per entendre les necessitats computacionals de problemes de disciplines diferents de la informàtica i efectuar contribucions significatives en equips multidisciplinaris que facin servir la computació.
Competències Tècniques Generals
Genèriques
CG1 - Capacitat per aplicar el mètode científic en l'estudi i anàlisi de fenòmens i sistemes en qualsevol àmbit de la Informàtica, així com en la concepció, disseny i implantació de solucions informàtiques innovadores i originals.
CG3 - Capacitat per al modelatge matemàtic, càlcul i disseny experimental en centres tecnològics i d'enginyeria d'empresa, particularment en tasques de recerca i innovació en tots els àmbits de la Informàtica.
Competències Transversals
Raonament
CTR6 - Capacitat de raonament crític, lògic i matemàtic. Capacitat de resoldre problemes en la seva àrea d'estudi. Capacitat d'abstracció: capacitat de crear i utilitzar models que reflecteixin situacions reals. Capacitat de dissenyar i realitzar experiments senzills, i analitzar-ne i interpretar-ne els resultats. Capacitat d'anàlisi, de síntesi i d'avaluació.
Bàsiques
CB8 - Que els estudiants sàpiguen comunicar les seves conclusions i els coneixements i raons darreres que les sustenten- a públics especialitzats i no especialitzats d'una manera clara i sense ambigüitats.
CB9 - Que els estudiants posseeixin les habilitats d'aprenentatge que els permetin continuar estudiant d'una manera que haurà de ser en gran mesura autodirigida o autònoma.
Continguts
Computational Models and Complexity Measures
Turing machine model. RAM model. Boolean circuit model.
Time complexity. Space complexity. Circuit size. Circuit depth.
Time and space hierarchy theorems.
P, NP and NP-completeness
Polynomial time. Reducibilities. Non-deterministic algorithms and class NP. Cook-Levin Theorem. Many other NP-complete problems.
Polynomial-time Hierarchy and Alternations
Oracle reducibility. NP and co-NP. Levels of the hierarchy. Quantifier alternations. Complete problems.
Randomized Computation
Bounded-error and zero-error probabilistic polynomial time. Error-reduction.
Randomized reductions. Valiant-Vazirani reduction to Unique SAT.
Counting and Enumeration
Some examples: graph reliability, counting matchings and the permanent, partition functions.
Counting computation paths in non-deterministic machines. Valiant's Theorem.
Random self-reducibility of the permanent.
Probabilistic Proofs
Interaction and randomness in proofs. Probabilistic proofs for graph non-isomorphism. Probabilistic proofs for #P and
Shamir's Theorem: IP = PSPACE.
Circuit Lower Bounds
Monotone circuits. Lower bounds for clique and perfect matching.
Bounded-depth circuits. Hastad's switching lemma.
Approximation by polynomials.
Activitats
ActivitatActe avaluatiu
Submission first problems sheet
Setmana:
3 Tipus:
entrega
Teoria
0h
Problemes
0h
Laboratori
0h
Aprenentatge dirigit
0h
Aprenentatge autònom
8h
Submission second problems sheet
Setmana:
6 Tipus:
entrega
Teoria
0h
Problemes
0h
Laboratori
0h
Aprenentatge dirigit
0h
Aprenentatge autònom
8h
Submission third problems sheet
Setmana:
9 Tipus:
entrega
Teoria
0h
Problemes
0h
Laboratori
0h
Aprenentatge dirigit
0h
Aprenentatge autònom
8h
Submission forth problems sheet
Setmana:
12 Tipus:
entrega
Teoria
0h
Problemes
0h
Laboratori
0h
Aprenentatge dirigit
0h
Aprenentatge autònom
8h
Submission fifth problems sheet
Setmana:
15 Tipus:
entrega
Teoria
0h
Problemes
0h
Laboratori
0h
Aprenentatge dirigit
0h
Aprenentatge autònom
8h
Final exam
Setmana:
18 Tipus:
examen final
Teoria
0h
Problemes
0h
Laboratori
0h
Aprenentatge dirigit
0h
Aprenentatge autònom
12h
Metodologia docent
Blackboard lectures for theory classes and discussion sessions for the problem classes. The theory classes will follow the main textbook for the class [Arora and Barak] rather closely. Since we plan to cover more topics than is possible in the given time, students will be required to read the details in the textbook as homework (a draft of the book is available on-line for free). The aim of the discussion sessions is to solve some problems from that book and to discuss the reading material.
Mètode d'avaluació
Students will be required to submit 5 problem/discussion sheets. Each will be given a grade in [0,1] (P1,...,P5).
There will be a final exam graded in [0,10] (E).
The final grade of the course will be MAX(P1+P2+P3+P4+P5+E/2, E).
The problem/discussion sheets will consist of problems from the main textbook [Arora-Barak] and/or multiple choice questions that test if the student understood the material from the theory class (also covered in the main textbook).