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
  • Maquinas de Turing
  • Regular Languages an its properties
  • Context Free Languages and its properties
  • Turing Machines
  • Introduction to Automata Theory Languages and Computation, J.E.Hopcroft and J.D.Ullman. Addison-Wesley 1979 (1st edition).
    • Chapters 2,3,4

26/02/2024

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

04/03/2024

  • 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

11/03/2024

  • Reduções polinomiais:
    • 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
  • Polynomial reductions:
    • 3Sat $\leq_P\; \neq$Sat
    • MaxCut \(\leq_P\) $\neq$-Sat
    • 3Sat \(\leq_P\) IRtPoly
    • 3Sat \(\leq_P\) $3$DM
    • 3DM \(\leq_P\) Par
  • co-NP class
  • Space complexity: Space and NSpace
  • PSpace and NPSpace
  • Savitch Theorem
  • PSpace-complete languages
  • Computational Complexity, Christos H. Papadimitriou. Chapter 9

18/03/2024

  • TQBF é PSPACE-completo
  • TQFB \(\leq_P\) Generalized-Geography
  • L & NL
  • Linguagens NL-completas
  • PATH é NL-completa
  • Teorema de Immerman–Szelepcsényi
  • 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.

08/04/2024

  • 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

15/04/2024

  • 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

22/04/2024

Teste intercalar

Midterm Test

29/04/2024

  • 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
  1. Prove that for every \(i\geq 1\), if \(\Sigma_i^p=\Pi_i^p\) then \(PH = \Sigma_i^p\) ; i.e. the Polynomial Hierarchy collapses at the $i$th level.
  2. Prove that \(\mathbf{ZPP}=\mathbf{RP}\cap\mathbf{coRP}\).

13/05/2024

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

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

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

  • \(\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,

20/05/2024

  • Complexidade Computacional média (Levin)

    • distP, distNP, distNP-completo
    • Existência de linguagens distNP-completas

  • Complexidade Kolmogorov e o argumento da incompressibilidade

    • 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".

    • Determininização de NFAs tem que ter casos exponenciais.

  • Desaleatorização

    • Noção de geradores pseudo-aletórios

    • Se existir um gerador $S(\ell)-$pseudo-aleatório então

      \(\mathbf{BPTIME}(S(\ell(n))\subseteq\mathbf{DTIME}(2^{cl(n)})\), para qualquer \(\ell\) computável em tempo polinomial.

    • As consequências de tal resultado.

  • Average Case Complexity (Levin)

    • distP, distNP, distNP-complete
    • Existence of distNP-complete languages

  • Kolmogorov Complexity and the incompressibility argument

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

  • Derandomization

    • Definition of pseudo-random generators.

    • If there exists a generator $S(\ell)-$pseudo-random then

      \(\mathbf{BPTIME}(S(\ell(n))\subseteq\mathbf{DTIME}(2^{cl(n)})\), for all for every polynomial-time computable function \(\ell\).

    • Consequences of such result.

  • Computational Complexity: A Modern Approach, Sangeev Agora & Boaz Barak. Cambridge University Press, 2009.
    • Chapters 18, 20.
  • Analysis of Sorting Algorithms by KolmogorovComplexity (ASurvey), Paul Vitányí. In "Entropy, Search, Complexity", Springer, 2007.

27/05/2024

  • Computação paralela
    • Classe \(\mathbf{NC}\)
    • \(\mathbf{NC}ˆ1\subseteq\mathbf{L}\)
    • \(\mathbf{N}\subseteq \mathbf{NC}ˆ2\)
    • \(\mathbf{NL}\subseteq \mathbf{NC}ˆ2\)
    • \(\mathbf{NC}\subseteq \mathbf{P}\)
    • CIRCUIT-VALUE é \mathbf{P}-completa
  • 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
    • Copiar 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øencias
  • \(\mathbf{BPP}\) e as classes de complexidade clássicas
  • Parallel computation
    • Class \(\mathbf{NC}\)
    • \(\mathbf{NC}ˆ1\subseteq\mathbf{L}\)
    • \(\mathbf{N}\subseteq \mathbf{NC}ˆ2\)
    • \(\mathbf{NL}\subseteq \mathbf{NC}ˆ2\)
    • \(\mathbf{NC}\subseteq \mathbf{P}\)
    • CIRCUIT-VALUE is \mathbf{P}-completa
  • Logically reversible computation
  • Physical reversible computation
  • Classical and quantum parity game
  • Elementary quantum operations (quantum gates)
    • Flipping qubits
    • Reordering qubits
    • Copying 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
Introduction to the Theory of Computation, Michael Sipser, section 10.5
  • Computational Complexity: A Modern Approach, Sangeev Agora & Boaz Barak. Cambridge University Press, 2009. Chapter 10.

Última modificação: 25/03/2025