Aula Prática 12

14 dezembro 2011, 08:30 • Maria Paula Antunes Abrantes Gouveia

Exercícios 1.3 e 3.3d da lista de exercícios para a aula prática 11. Exercícios 2.2 a) e 4.1 a) da lista de exercícios para a aula prática 12.

Aula Prática 11

13 dezembro 2011, 14:30 • Maria Paula Antunes Abrantes Gouveia

Exercícios 2.1, 2.3, 1.3 e 3.2 da lista de exercícios para a aula prática 11.

Aula Prática 12

13 dezembro 2011, 12:00 • Maria Paula Antunes Abrantes Gouveia

Exercícios 1.2 e 3.3d da lista de exercícios para a aula prática 11. Exercícios 2.2 a) e 4.1 a) da lista de exercícios para a aula prática 12.

Aula Teórica 19

13 dezembro 2011, 10:00 • Maria Paula Antunes Abrantes Gouveia

Proposição: P \subseteq PSPACE \subseteq EXPTIME \subseteq EXPSPACE. Prova informal da 1a e 3as inclusões. Proposição (só enunciado): P \está estritamente contido em EXPTIME e PSPACE \está estritamente contido em EXPSPACE. Problemas em aberto: P=PSPACE, PSAPCE=EXPTIME e EXPTIME=EXPSPACE.

Exemplos de linguagens/conjuntos/problemas em P: (i) existência de caminho entre dois nós de um grafo orientado, (ii) máximo divisor comum de dois naturais, (iii) determinar se uma palavra é ou não gerada por uma gramática livre de contexto. Exemplo de linguagem em EXPTIME mas não em P: {<M,w>: M aceita w em, no máximo 2^|w| passos}. Exemplo de linguagens/problemas para os quais não se conhecem classificadores em P: (i) circuitos hamiltonianos, (ii) problema do caixeiro viajante, (iii) SAT, (iv) factorização prima de um natural.

As classes NTIME(t), NSPACE(s), NP, NPSPACE, NEXPTIME, NEXPSPACE. Proposição (só enunciado): P \subseteq NP \subseteq PSPACE=NSPACE \subseteq EXPTIME \subseteq NEXPTIME \subseteq EXPSPACE=NEXPSPACE. Proposição (só enunciado): NP \está estritamente contido em NEXPTIME. Problemas em aberto: EXPTIME=NEXPTIME e P=NP. Noção informal de conjunto NP-completo. Relevância do problema P=NP e dos conjuntos NP-completos. Exemplos de conjuntos/problemas NP-completos: (i) circuitos hamiltonianos e (ii) SAT.

Aula Teórica 19

13 dezembro 2011, 08:30 • Maria Paula Antunes Abrantes Gouveia

Proposição: P \subseteq PSPACE \subseteq EXPTIME \subseteq EXPSPACE. Prova informal da 1a e 3as inclusões. Proposição (só enunciado): P \está estritamente contido em EXPTIME e PSPACE \está estritamente contido em EXPSPACE. Problemas em aberto: P=PSPACE, PSAPCE=EXPTIME e EXPTIME=EXPSPACE.

Exemplos de linguagens/conjuntos/problemas em P: (i) existência de caminho entre dois nós de um grafo orientado, (ii) máximo divisor comum de dois naturais, (iii) determinar se uma palavra é ou não gerada por uma gramática livre de contexto. Exemplo de linguagem em EXPTIME mas não em P: {<M,w>: M aceita w em, no máximo 2^|w| passos}. Exemplo de linguagens/problemas para os quais não se conhecem classificadores em P: (i) circuitos hamiltonianos, (ii) problema do caixeiro viajante, (iii) SAT, (iv) factorização prima de um natural.

As classes NTIME(t), NSPACE(s), NP, NPSPACE, NEXPTIME, NEXPSPACE. Proposição (só enunciado): P \subseteq NP \subseteq PSPACE=NSPACE \subseteq EXPTIME \subseteq NEXPTIME \subseteq EXPSPACE=NEXPSPACE. Proposição (só enunciado): NP \está estritamente contido em NEXPTIME. Problemas em aberto: EXPTIME=NEXPTIME e P=NP. Noção informal de conjunto NP-completo. Relevância do problema P=NP e dos conjuntos NP-completos. Exemplos de conjuntos/problemas NP-completos: (i) circuitos hamiltonianos e (ii) SAT.