Rogério Reis


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


Sumários

23/02/2026

  • 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

02/03/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).
  • 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.
  • 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).
  • Turing machine's Recursion theorem and its consequence on the unrecognisability of minimal Turing machines.
  • 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)

09/03/2026 (3)

  • 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.
  • 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
  • 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
  • Cook-Levin Theorem (Sat is $NP$-Complete)
  • Reductions:
    • 3Sat \(\leq_P\) Clique
    • 3Sat \(\leq_P\) VertexCover
    • 3Sat \(\leq_P\) HamPath
    • 3Sat \(\leq_P\) SubSetSum
  • - Computational Complexity: A Modern Approach, Sangeev Agora & Boaz Barak. Cambridge University Press, 2009. Chapter 2

16/03/2026 (4)

  • Reduções:
    • 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
  • 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
  • Reductions:
    • 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
  • 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
  • Computational Complexity, Christos H. Papadimitriou. Chapter 9
  • Theory of Computation, Dexter Kozen, 2006, Springer. Chapters 4 and 8.

23/03/2026 (5)

  • 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

13/04/2026 (6)

  • 1º Teste
  • Midterm test

20/04/2026 (7)

  • Hierarquia Polinomial: \(\Sigma_i^p\), \(\Pi_i^p\) e \(\mathbf{PH}\)
  • Consequências do colapso de algum nível da hierarquia
  • 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

27/04/2026 (8)

  • 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\)
  • Reduções aleatorizadas
  • \(\mathbf{BP\cdot NP}\) e \(\mathbf{RL}\)
  • UPath$\in\mathbf{RL}$
  • Classes \(\mathbf{BPL}\) e \(\mathbf{RL}\)
  • 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\)
  • Randomised reductions
  • \(\mathbf{BP\cdot NP}\) and \(\mathbf{RL}\)
  • UPath$\in\mathbf{RL}$
  • Classes \(\mathbf{BPL}\) and \(\mathbf{RL}\)
  • Computational Complexity: A Modern Approach, Sangeev Agora & Boaz Barak. Cambridge University Press, 2009. Chapter 7

11/05/2026 (9)

  • 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\)

  • \(\mathbf{IP}=\mathbf{PSPACE}\)

  • 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\)

  • \(\mathbf{IP}=\mathbf{PSPACE}\)

  • 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.
  • A. Shamir, IP = PSPACE , Journal of ACM, 39 (4) 1992 pag. 869-877,

18/05/2026 (10)

  • Complexidade Kolmogorov e o argumento da incompressibilidade

    • Complexidade Kolmogorov e Linguagens Formais

    • A complexidade de uma TM que reconheça a linguagem de palíndromos.

    • A complexidade média da imprementação da soma de dois registos pelo método "no-carry".

    • Complexidade média do "Bubble-Sort".

  • Kolmogorov Complexity and the incompressibility argument

    • Kolmogorov Complexity and Formal Languages.

    • The lower bound of a TM recognizing the palindromes' language.

    • The average complexity of the algorithm to add two registers with the "no-carry" method.

    • The determinisation of NFA's must have exponential blowups.

  • M. Li and P. Vitányi, An Introduction to Kolmogorov Complexity and Its Applications Chap. 6
  • Kolmogorov Complexity and its Applications, Ming Li and Paul Nitanyi in HANDBOOK OF THEORETICAL COMPUTER SCIENCE, J. van Leeuwen (Ed.),
  • Analysis of Sorting Algorithms by KolmogorovComplexity (ASurvey), Paul Vitányí. In "Entropy, Search, Complexity", Springer, 2007.

25/05/2026 (11)

  • Complexidade da Contagem

    • Definição da classe \(\#P\) e linguagens #P-completas

    • \(\#Cycle \in FP \Rightarrow P= NP\).

    • Teorema de Ladner: Se \(P\neq NP\) então existe uma linguagem em \(NP\setminus P\) que não é $NP$-completa

    • #3Sat é #P-completa.

    • Teorema de Valiant: \(perm\) para matrizes com entradas em \(\{0,1\}\) é #P-completa

    • Teorema de Toda: \(PH\subseteq P^{\#Sat}\)

  • Complexity of Counting

    • Definition of the class #P and of #P-complete languages

    • \(\#Cycle \in FP \Rightarrow P= NP\).

    • Ladner's Theorem: If \(P\neq NP\) then there exists a non NP-complete language in \(NP\setminus P\).

    • #3Sat is #P-complete

    • Valiant's Theorem: \(perm\) for ${0,1}$-matrices is #P-complete

    • Toda's Theorem: \(PH\subseteq P^{\#Sat}\)

  • Theory of Computation, Dexter Kozen, 2006, Springer. Chapters F & G
  • Computational Complexity: A Modern Approach, Sangeev Agora & Boaz Barak. Cambridge University Press, 2009. Chapter 17

01/06/2026 (12)

  • Computação logicamente reversível
  • Computação fisicamente reversível
  • O jogo da paridade, clássico e quântico
  • Operações quânticas elementares (portas quânticas)
    • Alterar o valor de um qubit
    • Reordenar quibits
    • "Duplicar" qbuits
    • Rotação de um qubit
    • Conjunção lógica de qubits
    • A operação de Hadamard
  • Definição de computação quântica
  • A classe de complexidade \(\mathbf{BPP}\)
  • \(\mathbf{BPP}\subseteq\mathbf{BQP}\)
  • O algorithmo de Shor para factorizar inteiros e as suas consequências
  • \(\mathbf{BPP}\) e as classes de complexidade clássicas
  • Logically reversible computation
  • Physical reversible computation
  • Classical and quantum parity game
  • Elementary quantum operations (quantum gates)
    • Flipping qubits
    • Reordering qubits
    • Contrloled "cloning" of qubits
    • Rotation on single qubit
    • AND of two bits
    • The Hadamard operation
  • Definition of quantum computation
  • \(\mathbf{BPP}\) complexity class
  • \(\mathbf{BPP}\subseteq\mathbf{BQP}\)
  • The Shor algorithm of integer factorizing and its consequences
  • \(\mathbf{BPP}\) and classical complexity classes

  • Computational Complexity: A Modern Approach, Sangeev Agora & Boaz Barak. Cambridge University Press, 2009. Chapter 10.

Última modificação: 03/06/2026