Hierarchy theorems and its implications in structural complexity

31 outubro 2018, 16:00 • José Félix Costa

Space and time hierarchy theorems.

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

Central complexity classes (4/11)

26 outubro 2018, 10:00 • José Félix Costa

Criteria Ex^n, Bc, Bc^n and Bc*. Separation Ex^(n+1) =/= Ex^n. Separation Ex* =/= Ex^n. Bc-identification. Bc, Bc^n and Bc*-identification. Separation Bc^(n) =/= Bc^(n+1). Separations Bc^(n) =/= Bc*, for all n \in N. R \in Bc*.

Conclusion of Learning Theory

----------------

Introduction to Complexity

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.

Consistent scientists

24 outubro 2018, 16:00 • José Félix Costa

Consistent and class-consistent scientists for functions.

Separation between classes Ex, [Ex]^class-consistent and [Ex]^consistent.

Non-union theorem

19 outubro 2018, 10:00 • José Félix Costa

Computational classes TxtEx and Ex. Sets AEZ (almost everywhere zero) and SD (self-describing).

Blums' non-union theorem. (Self-reference as proof technique.)

R \not\in Ex. PrR \in Ex (Meyer and Ritchie's theorem).

Identification

17 outubro 2018, 16:00 • José Félix Costa

Identification by computable and non-computable scientists. Identification of sets and functions. Identification of classes of sets and sets of functions.

Ex-identification. TxtEx-identification.

Total computable scientists equivalents to partial scientists. Scientists for functions working with canonical text.

Proof of Blum and Blum locking sequence theorem. Locking sequences.