Rogério Reis


Err and err and err again, but less and less and less.


Sumários

23/02/2024

  • Linguagens regulares e suas propriedades
  • Linguagens independentes de contexto e suas propriedades
  • Regular Languages an its properties
  • Context Free Languages and its properties
  • Introduction to Automata Theory Languages and Computation, J.E.Hopcroft and J.D.Ullman. Addison-Wesley 1979 (1st edition).
    • Chapters 2,3,4

24/02/2025

  • Equivalência entre os diversos modelos de Máquinas de Turing
  • Linguagens reconhecíveis e decidíveis
  • Existência de linguagens não reconhecíveis e de linguagens não decidíveis. Exemplos de linguagens nestas condições.
  • O Teorema de Rice.
  • Reduções de liguagens e suas consequêncas de computabilidade.
  • A noção de Máquinas de Turing com fita limitada (LBA), a decidibilidade do seu problema da palavra e a não decidibilidade do problema da linguagem vazia.
  • O problema de correspondência de Post (PCP).
  • Equivalence of the various variants of Turing Machines.
  • Recognisable languages and decidable languages.
  • Languages unrecognisable and undecidable. Examples of these languages.
  • Rice's theorem.
  • Map reductions and its computability consequences.
  • Notion of Linear Bounded Automata (LBA), the decidability of its word problem and the undecidability of its empty language problem.
  • Post Correspondency Problem (PCP).
  • Introduction to Automata Theory Languages and Computation, J.E.Hopcroft and J.D.Ullman. Addison-Wesley 1979 (1st edition). Chapter 7 and 8 (sections 8.1-8.5)

10/03/2025

  • o Teorema da recursão para máquinas de Turing e sua consequência sobre a não reconhecibilidade de máquinas de Turing mínimas.
  • Notação Bachmann-Landau
  • Custo da simulação de uma TM com $k$-fitas e de uma TM não determinística por uma TM determinística com uma só fita.
  • A classe de complexidade \(P\).
  • Exemplos de linguagens em \(P\).
  • A classe de complexidade \(NP\).
  • Noção de redução polinomial.
  • Definição de linguagem $NP$-completa.
  • Turing machine's Recursion theorem and its consequence on the unrecognisability of minimal Turing machines.
  • Bachmann-Landau Notation
  • Cost of the simmulation of a $k$-tape Turing Machine and of a nondeterministic Turing Machine by a $1$-tape Turing Machine.
  • The class of complexity \(P\)
  • Some examples of languages in \(P\)
  • The class of complexity \(NP\)
  • Notion of polynomial reduction
  • Definition of $NP$-completness
  • - Computational Complexity: A Modern Approach, Sangeev Agora & Boaz Barak. Cambridge University Press, 2009. Chapter 2

Problems:

17/03/2025

  • O teorema de Cook-Levin (Sat é $NP$-completa).
  • Reduções:
    • 3Sat \(\leq_P\) Clique
    • 3Sat \(\leq_P\) VertexCover
    • 3Sat \(\leq_P\) HamPath
    • 3Sat \(\leq_P\) SubSetSum
    • 3Sat $\leq_P\; \neq$Sat
    • MaxCut \(\leq_P\) $\neq$-Sat
    • 3Sat \(\leq_P\) IRtPoly
    • 3Sat \(\leq_P\) $3$DM
    • 3DM \(\leq_P\) Par
  • Classe co-NP
  • Cook-Levin Theorem (Sat is $NP$-Complete)
  • Reductions:
    • 3Sat \(\leq_P\) Clique
    • 3Sat \(\leq_P\) VertexCover
    • 3Sat \(\leq_P\) HamPath
    • 3Sat \(\leq_P\) SubSetSum
    • 3Sat $\leq_P\; \neq$Sat
    • MaxCut \(\leq_P\) $\neq$-Sat
    • 3Sat \(\leq_P\) IRtPoly
    • 3Sat \(\leq_P\) $3$DM
    • 3DM \(\leq_P\) Par
  • Class co-NP
• Computational Complexity, Christos H. Papadimitriou. Chapter 9

24/03/2025

  • Complexidade por Espaço: Space e NSpace
  • PSpace and NPSpace
  • Teorema de Savitch
  • Linguagens PSpace-completas
  • TQBF é PSPACE-completo
  • TQFB \(\leq_P\) Generalized-Geography
  • L & NL
  • Linguagens NL-completas
  • PATH é NL-completa
  • Teorema de Immerman–Szelepcsényi
  • Space complexity: Space and NSpace
  • PSpace and NPSpace
  • Savitch Theorem
  • PSpace-complete languages
  • TQBF is PSPACE-complete
  • TQFB \(\leq_P\) Generalised-Geography
  • L & NL
  • NL-complete languages
  • PATH is NL-complete
  • Immerman–Szelepcsényi theorem
  • Theory of Computation, Dexter Kozen, 2006, Springer. Chapters 4 and 8.

31/03/2025

  • Teorema da hierarquia de espaço
  • Teorema da hirerarquia de tempo
  • Linguagens ExpSpace-completas
  • \(EQ_{REX\uparrow}\) é ExpSpace-completa
  • Noções elementares de complexidade de Kolmogorov
  • Space Hierarchy Theorem
  • Time Hierarchy Theorem
  • ExpSpace-complete languages
  • \(EQ_{REX\uparrow}\) is ExpSpace-complete
  • Notions of Kolmogorov complexity
  • Introduction to the theory of computation, Michael Sipper. 1997. Chapter 9

07/04/2025

  • Complexidade de circuitos boleanos
  • \(A\in TIME(f(n)) \Rightarrow A\in SIZE(f^2(n))\)
  • CircuitSat é NP-completa
  • A classe \(P_{/Poly}\)
  • Famílias de circuitos uniformemente gerados
  • Algoritmos aproximados
  • Boolean Circuit Complexity
  • \(A\in TIME(f(n)) \Rightarrow A\in SIZE(f^2(n))\)
  • CircuitSat is NP-complete
  • Complexity class \(P_{/Poly}\)
  • Circuit Families Uniformly generated
  • Aproximated Algorithms
  • Introduction to the Theory of Computation, Michael Sipser
    • Chapters 9.3 and 10.1

13/05/2025

  • Hierarquia Polinomial: \(\Sigma_i^p\), \(\Pi_i^p\) e \(\mathbf{PH}\)
  • Consequências do colapso de algum nível da hierarquia
  • Máquinas de Turing probalilísticas
  • Definição de \(\mathbf{BTIME}(t(n))\) e \(\mathbf{BPP}\)
  • Algoritmos probabilísticos para:
    • encontrar a mediana de uma lista
    • primalidade de um inteiro
    • anulação de um polinómio dado por um circuito algébrico
  • Lema de ampliação
  • Tempo esperado de execução
  • Definição de \(\mathbf{RPTIME}(t(n))\) e \(\mathbf{RP}\)
  • Definição de \(\mathbf{ZTIME}(t(n))\) e \(\mathbf{ZPP}\)
  • \(\mathbf{BPP}\subseteq \mathbf{P}_{/poly}\)
  • Teorema de Sipser-Gács: \(\mathbf{BPP}\subseteq \Sigma_2^p\cap\Sigma_2^p\)
  • Polynomial Hierarchy: \(\Sigma_i^p\), \(\Pi_i^p\) e \(\mathbf{PH}\)
  • Consequences of the colapse of a level of the hierarchy
  • Probabilistic Turing Machines
  • Definition of \(\mathbf{BTIME}(t(n))\) and \(\mathbf{BPP}\)
  • Probabilistic algorithms for:
    • median of a set
    • primality
    • nullement of a polynomial described as an algebraic circuit
  • Expected time of execution
  • Definition of \(\mathbf{RPTIME}(t(n))\) and \(\mathbf{RP}\)
  • Definition of de \(\mathbf{ZTIME}(t(n))\) and \(\mathbf{ZPP}\)
  • \(\mathbf{BPP}\subseteq \mathbf{P}_{/poly}\)
  • Sipser-Gács Theorem: \(\mathbf{BPP}\subseteq \Sigma_2^p\cap\Sigma_2^p\)
  • Computational Complexity: A Modern Approach, Sangeev Agora & Boaz Barak. Cambridge University Press, 2009. Chapter 7

19/05/2025

  • Reduções aleatorizadas

  • \(\mathbf{BP\cdot NP}\) e \(\mathbf{RL}\)

    • UPath$\in\mathbf{RL}$

  • Demonstrações interactivas

  • \(\mathbf{dIP}=\mathbf{NP}\)

  • \(\mathbf{IP}(f(n)\) e \(\mathbf{IP}\)

    • Demonstração interactiva para o não-isomorfimo de grafos
    • IDemonstração interactiva para residuzidade quatrática

  • $\mathbf{AM}$-demonstrações

  • \(\mathbf{IP}[k]\subseteq\mathbf{AM}[k + 2]\).

  • GNI \(\in\mathbf{AM}[2]\).

  • GI is NP-complete \(\implies \Sigma_2^p = \Pi_2^p\)

  • Randomised reductions

  • \(\mathbf{BP\cdot NP}\) and \(\mathbf{RL}\)

    • UPath$\in\mathbf{RL}$

  • Interactive proofs

  • \(\mathbf{dIP}=\mathbf{NP}\)

  • \(\mathbf{IP}(f(n)\) and \(\mathbf{IP}\)

    • Interactive proof for graph non-isomorphism
    • Interactive proof for quadratic non-residuosity

  • $\mathbf{AM}$-proofs

  • \(\mathbf{IP}[k]\subseteq\mathbf{AM}[k + 2]\).

  • GNI \(\in\mathbf{AM}[2]\).

  • GI is NP-complete \(\implies \Sigma_2^p = \Pi_2^p\)

  • Computational Complexity: A Modern Approach, Sangeev Agora & Boaz Barak. Cambridge University Press, 2009. Chapter 8
  • S. Goldwasser and M. Sipser, Private coins vs. public coins in interactive proof systems, in Proc. 18th Symp. Theory of Computing, ACM, May 1986, pp. 59–68.

Última modificação: 20/05/2025