FenixEdu™

Sumários

Characterization of P = PSPACE and P = NP

31 outubro 2013, 12:30 • José Félix Costa

Honest functions.

One-way functions.

Concept of a guess.

Characterization of P in terms of functions: a set is in P iff it is the range of a function computable in polynomial time with an inverse computable in polinomial time.

Characterization of NP in terms of functions: a set is in NP iff it is the range of an honest function computable in polynomial time.

Charaterization of P = PSPACE.

Characterization of P = NP: The structural relation P = NP holds iff ANY honest functions computable in polinomial time has ONE INVERSE computable in polinomial time.

Exercises:

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

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.

Central complexity classes

25 outubro 2013, 10:30 • José Félix Costa

Classes DTIME(t), DSPACE(s), NTIME(t) and NSPACE(s) for time and space resources t and s, respectively.

Central complexity classes: LOG, NLOG, P, NP, PSPACE, NPSPACE, DEXT, NEXT, EXPSPACE, EXPTIME, NEXPTIME.

Theorem [Structural relations between classes DTIME, NTIME, DSPACE e NSPACE]: Let s(n) >= 1, s'(n) >= 1, t(n) >= n+1 e t'(n) >= n+1 be total functions:

DTIME(t) incl. NTIME(t) and DSPACE(s) incl. NSPACE(s);

DTIME(t) incl. DSPACE(t) and NTIME(t) incl. NSPACE(t);

If s' in O(s), then DSPACE(s') incl. DSPACE(s) and NSPACE(s') incl. NSPACE(s);

If t' in O(t) and n in o(t), então DTIME(t') incl. DTIME(t) and NTIME(t') incl. NTIME(t);

If t is constructible, then NTIME(t) incl. DSPACE(t);

If s' in Teta(s), then DSPACE(s') = DSPACE(s) and NSPACE(s') = NSPACE(s);

If t' in Teta(t) and n in o(t), then DTIME(t') = DTIME(t);

If s is constructible and s(n) >= log n, then NSPACE(s) incl. DTIME(2^O(s));

If t is constructible, then NTIME(t) incl. DSPACE(t);

If s is constructible, s(n) >= log n, então DSPACE(s) incl. DTIME(2^O(s));

If t is constructible, então NTIME(t) incl. DTIME(2^O(t)).

Savitch theorem (divide to conquer technique).

Immerman||Szelepcsényi theorem.

Diagram of relations between basic classes DTIME(t(n)), DTIME(2^O(t(n))), DSPACE(t(n)), DSPACE(t(n)^2), NTIME(t(n)), NSPACE(t(n)), co-NSPACE(t).

Properties:

(a) Deterministic classes are closed under complementation;

(b) Deterministic classes are contained in their non-deterministic counter part;

(d) PSPACE = NPSPACE;

(e) NP is included in PSPACE, PSPACE is included in EXPTIME.

Buzy Beaver

24 outubro 2013, 12:30 • José Félix Costa

Hierarchy theorems and Borodin's theorem: the trouble with constructibility of functions.

Computational classes and growing rates: P, E (Elementary functions), PR (primitive recursive functions), R (total recursive functions).

The Busy Beaver.

Link to the Busy Beaver.

Teoremas de hierarquia

18 outubro 2013, 10:30 • José Félix Costa

Teorema da hierarquia do espaço: Se s' in \omega(s) é construtível no spaço, então DSPACE(s') contém pelo menos um conjunto que não pertence a DSPACE(s) [do ponto de vista prático, a condição suficiente s' in ómega(s) pode ser substituída por lim s(n)/s'(n)=0].

Teorema da hierarquia do tempo: Se t' in ómega(t.log t) é construtível, então DTIME(t') contém pelo menos um conjunto que não pertence a DTIME(t).

Constructible functions

17 outubro 2013, 12:30 • José Félix Costa

Upper bound on the number of configurations of a space bounded Turing machine. Decidability of the halting problem of space-bounded Turing machines.

Relation between time and space resources of Turing machines.

Time and space constructible functions.

Theorem [tape compression]: If a is decidable by a deterministic (non-deterministic) Turing machine M in space s and c is real number such that 0 < c < 1, then A is decidable by a deterministic (non-deterministic) Turing machine M' in space c.s(n).

Theorem [speedup linear]: If A is decidable by a deterministic (non-deterministic) Turing machine in time t, with n in o(t(n)) e 0 < c < 1, then A is decidable by a deterministic (non-deterministic) Turing machine in time c t.

Theorem [reduction of the number of tapes]: If M is a Turing machine M deciding A in time t(n), then there exists a deterministic Turing machine that decides A in time O(t(n).log t(n)).