Sumários
17/02/2023
- 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
24/02/2023
- 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)
03/03/2023
- 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 lingaugens 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
10/03/2023
- 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
17/03/2023
- 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.
24/03/2023
- 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
14/04/2023
- 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
21/04/2023
- 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
28/04/2023
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
05/03/2023
\(\mathbf{IP}=\mathbf{PSPACE}\)
Complexidade Computacional média (Levin)
- distP, distNP, distNP-completo
- Existência de linguagens distNP-completas
\(\mathbf{IP}=\mathbf{PSPACE}\)
Average Case Complexity (Levin)
- distP, distNP, distNP-complete
- Existence of distNP-complete languages
- Computational Complexity: A Modern Approach, Sangeev Agora & Boaz Barak. Cambridge University Press, 2009.
- Chapters 8, 18
- 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 pp. 869-877.
19/05/2023
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.
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. Chapter 20.
- Analysis of Sorting Algorithms by KolmogorovComplexity (ASurvey), Paul Vitányí. In "Entropy, Search, Complexity", Springer, 2007.
24/05/2023
- 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
- 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
- Computational Complexity: A Modern Approach, Sangeev Agora & Boaz Barak. Cambridge University Press, 2009. Chapter 10.
Última modificação: 25/04/2024