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
- 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.
- Prove that \(\mathbf{ZPP}=\mathbf{RP}\cap\mathbf{coRP}\).
Última modificação: 30/04/2024