Complexidade Computacional 2024-2025

Sumários

Introduction to Automata Theory Languages and Computation, J.E.Hopcroft and J.D.Ullman. Addison-Wesley 1979 (1st edition).

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

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

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)

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

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

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

• Computational Complexity, Christos H. Papadimitriou. Chapter 9

Show that $TIME(2^n)=TIME(2^{n+1})$.
Show that $TIME(2^n)\subsetneq TIME(2^{2n})$.
Show that $NTIME(n)\subsetneq PSPACE$.
Give regular expressions with exponentiation that generate the following languages with alphabet $\{0,1\}$:
1. All words of size $500$.
2. All words of size $500$ or less.
3. All words of size $500$ or more.
4. All words of size that is nor $500$.
Show that $A_{DFA}=\{\langle A,w\rangle\mid A\text{ is }DFA\text{ and }w\text{is accepted by }A\}\in L$
Define $\text{Cycle}=\{\langle G\rangle\mid G\text{is a digraph with a cycle }\}$. Show that Cycle is NL-complete.

Última modificação: 06/04/2025

Rogério Reis