P13-T2 Décima terceira aula prática (Turma 2)

14 dezembro 2012, 08:00 • Francisco Miguel Alves Campos de Sousa Dionísio

Relógio n^2. Fecho de PSpace para a interseção e fecho de P para a diferença de conjuntos.

TURMA 106: Classes P e PSPACE

13 dezembro 2012, 09:30 • José Félix Costa

Exercício: Mostre que as classes P e PSPACE estão booleanamente fechadas.

Exercício: Mostre que se f é uma função computável em tempo polinomial, então, para todo o x, f-1(x) está em P.

Exercício: Mostre que se f é uma função computável em tempo polinomial e A um conjunto decidível em tempo polinomial, então f-1(A) está em P.

TPC

Exercício: Mostre que um conjunto está em P se e só se é o contradomínio de uma função unária computável em tempo polinomial que tem inversa computável em tempo polinomial.

P13-T3 Décima terceira aula prática  (Turma 3)

13 dezembro 2012, 08:00 • Francisco Miguel Alves Campos de Sousa Dionísio

Relógio n^2. Fecho de PSpace para a interseção e fecho de P para a diferença de conjuntos.

Complexidade III

12 dezembro 2012, 11:00 • José Félix Costa

Caracterização preliminar das classes NTIME e NSPACE:

(a) NTIME(t) incl. DSPACE(t);

(b) NSPACE(s) incl. DTIME(2^O(s)).

Propriedades de classes de complexidade:

(a) Toda a classe determinística está fechada para a complementação;

(b) P está contida em PSPACE, PSPACE está contida em EXPTIME.

Alguns problemas em aberto em complexidade estrutural: P =?= PSPACE.

Complexidade III

12 dezembro 2012, 09:30 • José Félix Costa

Caracterização preliminar das classes NTIME e NSPACE:

(a) NTIME(t) incl. DSPACE(t);

(b) NSPACE(s) incl. DTIME(2^O(s)).

Propriedades de classes de complexidade:

(a) Toda a classe determinística está fechada para a complementação;

(b) P está contida em PSPACE, PSPACE está contida em EXPTIME.

Alguns problemas em aberto em complexidade estrutural: P =?= PSPACE.