Savitch theorem

29 outubro 2014, 10:00 • José Félix Costa

Simulations of NSPACE(s(n)) in exponential time in s(n).

Savitch theorem (divide to conquer technique).

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

Diagram of relations between central complexity clases: LOG, NLOG, P, DEXT, EXPTIME, NP, PSPACE, NPSPACE, EXPSPACE, co-NLOG.

**END OF CHAPTER COMPLEXITY CLASSES**

Central complexity classes

24 outubro 2014, 11:00 • José Félix Costa

Non-deterministic Turing machines. Role of non-determinism in non-deterministic computation.

Classes 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: If t is constructible, then NTIME(t) incl. DSPACE(t).

=====================================================================

Exercise: Prove the following structural relations between classes DTIME, NTIME, DSPACE e NSPACE (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, 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)).

Time hierarchy theorem

22 outubro 2014, 10:00 • José Félix Costa

Theorem [tape compression]: If A is decidable by a deterministic (non-deterministic) Turing machine M in space s then, for every c \in N-{0}, A is decidable by a deterministic (non-deterministic) Turing machine M' in space s(n)/c.

Theorem [linear speedp]: If A is decidable by a deterministic (non-deterministic) Turing machine M in time t, with n in o(t(n)), then, for every c \in N-{0}, A is decidable by a deterministic (non-deterministic) Turing machine M' in time t(n)/c

Theorem [time hierarchy]: If t'(n) in \omega(t(n).log(t(n)) is time constructible, then DTIME(t'(n)) contains a set that does not belong to DTIME(t(n)).

Space hierarchy theorem

17 outubro 2014, 11:00 • José Félix Costa

Complexidade and the growing of functions. The Busy Beaver.

Borodin-Trakhtenbrot Gap Theorem. The requirement of constructibility.

Teorema da hierarquia do espaço (Lewis, Stearns, and Hartmanis): Se s' in \omega(s) é construtível no spaço, então DSPACE(s') contém pelo menos uma linguagem 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].

Central complexity classes I

15 outubro 2014, 10:00 • 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.

Classes DTIME(t) and DSPACE(s), for time and space resources t and s, respectively. Central complexity classes: LOG, P, PSPACE, DEXT, EXPSPACE, EXPTIME. First structural relations.