Sumários

AND-OR circuits

12 Novembro 2021, 08:30 José Félix Costa

Riordan's and Shannon's Theorem.

Algorithm to convert classical Boolean circuits in AND-OR circuits.
Exponential size circuits.
The CVP decision problem.
Simulating bounded resources Turing machines with families of circuits.

--- END OF TERM 1 ---


Circuits

10 Novembro 2021, 16:00 José Félix Costa

Boolean circuits. Examples. Size and Depth.
Circuit families.


Hierarchy theorems and its implications in structural complexity (part 2)

5 Novembro 2021, 08:30 José Félix Costa

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

Space and time hierarchy theorems.

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


Hierarchy theorems and its implications in structural complexity (part 1)

3 Novembro 2021, 16:00 José Félix Costa

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

Space and time hierarchy theorems.

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


Test 1

29 Outubro 2021, 08:30 José Félix Costa

TEST 1.