Last update: T_KTI (16.05.2011)
- Partial input, subcube, monomial, DNF, implicant, primary implicant.
- Clause, CNF, implicate, prime implicate.
- Dual function, monotone, self-dual and linear funciotns.
- Boolean formulas, circuits.
- Binary decision tree, binary decision diagrams (BDD), read-once BDD, OBDD.
- Diagram of mutual relationships between the studied models, proofs of embeddings in it.
- The maximum complexity of representing functions using circuits and binary decision diagrams.
- Bounds on the complexity of functions in DNF, CNF, decision trees.
- Bounds on the complexity of OBDD and read-once BDD.
- Diagram of mutual relationships between the studied models, proofs of strict inclusions and incomparabilitites.
- Operations with functions represented by OBDD.
- The relationship between the depth and size of a decision tree and the complexity of the function expressed by both DNF and CNF.
- Operations with functions represented using decision trees.
- Nonuniform Turing machine, relationship to Boolean models, Karp-Lipton theorem.
- Probabilistic non-equivalence test for read-once decision diagrams.
- BPP is contained in P/poly, so is representable by polynomial size circuits.
- Lower bounds for decision trees using Fourier transform of the Boolean functions.
Last update: T_KTI (05.05.2015)
- Zavedení zkoumaných modelů, Booleovské obvody, formule, rozhodovací diagramy (BDD), DNF, CNF, rozhodovací stromy, read-once BDD, uspořádané BDD (OBDD).
- Duální funkce, funkce monotonní, samoduální, lineární.
- Diagram vzájemných vztahů mezi zkoumanými modely (důkazy inkluzí).
- Složitost vyjádření funkcí pomocí DNF, CNF, rozhodovacích stromů.
- Hloubka a velikost stromu pro funkci vyjádřenou současně pomocí DNF a CNF.
- Odhady maximální složitosti obvodů a rozhodovacích diagramů.
- Odhady složitosti pro OBDD a read-once BDD.
- Diagram vzájemných vztahů mezi zkoumanými modely (ostré inkluze a neporovnatelnosti).
- Operace s funkcemi reprezentovanými pomocí OBDD a rozhodovacích stromů.
- Neuniformní Turingův stroj, souvislost s Booleovskými modely, Karp-Liptonova věta.
- Pravděpodobnostní test ekvivalence pro read-once rozhodovací diagramy.
- BPP je podmožina P/poly, tedy lze reprezentovat obvody polynomiální velikosti.
|