Complejidad Computacional

Créditos
6
Tipos
Obligatoria de especialidad (Computación Avanzada)
Requisitos
Esta asignatura no tiene requisitos , pero tiene capacidades previas
Departamento
CS
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.

Profesorado

Responsable

Otros

Horas semanales

Teoría
2
Problemas
2
Laboratorio
0
Aprendizaje dirigido
0
Aprendizaje autónomo
4

Competencias

Competencias Técnicas de cada especialidad

Advanced computing

  • CEE3.1 - Capacidad para identificar barreras computacionales y analizar la complejidad de problemas computacionales en diversos ámbitos de la ciencia y la tecnología; así como para representar problemas de alta complejidad en estructuras matemáticas que puedan ser tratadas eficientemente con esquemas algorítmicos.
  • CEE3.3 - Capacidad para entender las necesidades computacionales de problemas de disciplinas distintas de la informática y efectuar contribuciones significativas en equipos multidisciplinares que usen la computación.

    • Competencias Técnicas Genéricas

    Genéricas

  • CG1 - Capacidad para aplicar el método científico en el estudio y análisis de fenómenos y sistemas en cualquier ámbito de la Informática, así como en la concepción, diseño e implantación de soluciones informáticas innovadoras y originales.
  • CG3 - Capacidad para el modelado matemático, cálculo y diseño experimental en centros tecnológicos y de ingeniería de empresa, particularmente en tareas de investigación e innovación en todos los ámbitos de la Informática.

    • Competencias Transversales

    Razonamiento

  • CTR6 - Capacidad de razonamiento crítico, lógico y matemático. Capacidad para resolver problemas dentro de su área de estudio. Capacidad de abstracción: capacidad de crear y utilizar modelos que reflejen situaciones reales. Capacidad de diseñar y realizar experimentos sencillos, y analizar e interpretar sus resultados. Capacidad de análisis, síntesis y evaluación.

    • Básicas

  • CB8 - Que los estudiantes sepan comunicar sus conclusiones y los conocimientos y razones últimas que las sustentan a públicos especializados y no especializados de un modo claro y sin ambigüedades.
  • CB9 - Que los estudiantes posean las habilidades de aprendizaje que les permitan continuar estudiando de un modo que habrá de ser en gran medida autodirigido o autónomo.

    • Contenidos

    1. 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.
    2. P, NP and NP-completeness
      Polynomial time. Reducibilities. Non-deterministic algorithms and class NP. Cook-Levin Theorem. Many other NP-complete problems.
    3. Polynomial-time Hierarchy and Alternations
      Oracle reducibility. NP and co-NP. Levels of the hierarchy. Quantifier alternations. Complete problems.
    4. Space Complexity
      Polynomial space. Unbounded alternations. PSPACE-complete problems.
      Savitch Theorem. Immerman-Szcelepscenyi Theorem.
      Logarithmic space. NL-complete problems.
    5. Randomized Computation
      Bounded-error and zero-error probabilistic polynomial time. Error-reduction.
      Randomized reductions. Valiant-Vazirani reduction to Unique SAT.
    6. 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.
    7. Probabilistic Proofs
      Interaction and randomness in proofs. Probabilistic proofs for graph non-isomorphism. Probabilistic proofs for #P and
      Shamir's Theorem: IP = PSPACE.
    8. Circuit Lower Bounds
      Monotone circuits. Lower bounds for clique and perfect matching.
      Bounded-depth circuits. Hastad's switching lemma.
      Approximation by polynomials.

    Actividades

    Actividad Acto evaluativo


    Submission first problems sheet



    Semana: 3
    Teoría
    0h
    Problemas
    0h
    Laboratorio
    0h
    Aprendizaje dirigido
    0h
    Aprendizaje autónomo
    0h

    Submission second problems sheet



    Semana: 6
    Teoría
    0h
    Problemas
    0h
    Laboratorio
    0h
    Aprendizaje dirigido
    0h
    Aprendizaje autónomo
    0h

    Submission third problems sheet



    Semana: 9
    Teoría
    0h
    Problemas
    0h
    Laboratorio
    0h
    Aprendizaje dirigido
    0h
    Aprendizaje autónomo
    0h

    Submission forth problems sheet



    Semana: 12
    Teoría
    0h
    Problemas
    0h
    Laboratorio
    0h
    Aprendizaje dirigido
    0h
    Aprendizaje autónomo
    0h

    Submission fifth problems sheet



    Semana: 15
    Teoría
    0h
    Problemas
    0h
    Laboratorio
    0h
    Aprendizaje dirigido
    0h
    Aprendizaje autónomo
    0h

    Final exam



    Semana: 18
    Teoría
    0h
    Problemas
    0h
    Laboratorio
    0h
    Aprendizaje dirigido
    0h
    Aprendizaje autónomo
    0h

    Metodología docente

    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étodo de evaluación

    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).

    Bibliografía

    Básico

    Complementario