Complexidade Computacional 2023-2024

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 $\neq$ -Sat
- 3Sat $\leq_P$ IRtPoly
- 3Sat $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 $\neq$ -Sat
- 3Sat $\leq_P$ IRtPoly
- 3Sat $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 then ; i.e. the Polynomial Hierarchy collapses at the $i$ th level.
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: 27/05/2025

Rogério Reis

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

23/02/2024

26/02/2024

04/03/2024

11/03/2024

18/03/2024

08/04/2024

15/04/2024

22/04/2024

Teste intercalar

Midterm Test

29/04/2024

13/05/2024

20/05/2024

27/05/2024