Diplomová práce je rozdělena do tří částí. V první části připomeneme několik základních faktů z teorie výpočetní složitosti, zavedeme standardní výpočetní model zvaný Turingův stroj a pomocí něho definujeme několik složitostních tříd.
V další části se budeme podrobněji zabývat problémy s logaritmickou prostorovou
složitostí a obzvlášt třídami NL a UL. Panuje obecné přesvědčení o tom, že se tyto třídy sobě rovnají, ale problém zůstává otevřeným. Na konci této části připomeneme některé techniky, které se využívají při práci s třídami problémů řešitelných v logaritmickém prostoru.
V poslední části dokážeme hlavní výsledek této práce: tvrzení, že problém souvislosti orientovaného grafu na podmnožině třídy mřížkových grafů patří do UL.
Annotation in English
Diploma thesis is divided into three parts. In the first part we review some
basic facts of the computational complexity theory, present a standard model of
computation called Turing machine and use it to define some complexity classes.
In the next part we take a closer look at the logarithmic space complexity classes
and especially the classes NL and UL. It is believed that these classes are equal
but the problem remains open. At the end of this part we recall some techniques
for working with classes using logarithmic space.
In the last part we prove the main result of this thesis: the directed connectivity problem on a restricted subclass of grid graphs belongs to UL.
Keywords
Teorie výpočetní složitosti, prostorová složitost, logaritmický prostor, log-space, jednoznačný log-space, mřížkové grafy, min-unique grafy, problém souvislosti orientovaného grafu
Keywords in English
Computational complexity theory, space complexity, logarithmic space, log-space,
unambiguous log-space, grid graphs, min-unique graphs, directed connectivity problem
Length of the covering note
38
Language
AN
Annotation
Diplomová práce je rozdělena do tří částí. V první části připomeneme několik základních faktů z teorie výpočetní složitosti, zavedeme standardní výpočetní model zvaný Turingův stroj a pomocí něho definujeme několik složitostních tříd.
V další části se budeme podrobněji zabývat problémy s logaritmickou prostorovou
složitostí a obzvlášt třídami NL a UL. Panuje obecné přesvědčení o tom, že se tyto třídy sobě rovnají, ale problém zůstává otevřeným. Na konci této části připomeneme některé techniky, které se využívají při práci s třídami problémů řešitelných v logaritmickém prostoru.
V poslední části dokážeme hlavní výsledek této práce: tvrzení, že problém souvislosti orientovaného grafu na podmnožině třídy mřížkových grafů patří do UL.
Annotation in English
Diploma thesis is divided into three parts. In the first part we review some
basic facts of the computational complexity theory, present a standard model of
computation called Turing machine and use it to define some complexity classes.
In the next part we take a closer look at the logarithmic space complexity classes
and especially the classes NL and UL. It is believed that these classes are equal
but the problem remains open. At the end of this part we recall some techniques
for working with classes using logarithmic space.
In the last part we prove the main result of this thesis: the directed connectivity problem on a restricted subclass of grid graphs belongs to UL.
Keywords
Teorie výpočetní složitosti, prostorová složitost, logaritmický prostor, log-space, jednoznačný log-space, mřížkové grafy, min-unique grafy, problém souvislosti orientovaného grafu
Keywords in English
Computational complexity theory, space complexity, logarithmic space, log-space,
unambiguous log-space, grid graphs, min-unique graphs, directed connectivity problem
Research Plan
Studium literatury k problematice prostorové výpočetní složitosti se zřetelem k vlastnostem třídy Log-space a zpracování jejích základů v přehledové části diplomové práce.
Studium základních matroidových algoritmů a technik, zpracování v přehledové části práce. Lze se omezit na oblast související s problémem zvoleným v bodu 3.
Průzkum zvolené otevřené otázky se vztahem k prostorové složitosti grafové nebo matroidové úlohy, formulace a studium přirozených modifikací dané otázky.
Research Plan
Studium literatury k problematice prostorové výpočetní složitosti se zřetelem k vlastnostem třídy Log-space a zpracování jejích základů v přehledové části diplomové práce.
Studium základních matroidových algoritmů a technik, zpracování v přehledové části práce. Lze se omezit na oblast související s problémem zvoleným v bodu 3.
Průzkum zvolené otevřené otázky se vztahem k prostorové složitosti grafové nebo matroidové úlohy, formulace a studium přirozených modifikací dané otázky.
Recommended resources
M. Sipser. Introduction to the Theory of Computation, 2nd Ed., Thomson, Boston, MA, 2006.
O. Reingold. Undirected connectivity in log-space, J. ACM 55, no. 4 (2008), 17:1--17:24.
S. Datta a G. Prakriya. Planarity testing revisited, in: Proc. 8th annual conference on Theory and Applications of Models of Computation, TAMC'11, Springer, Berlin, 2011, pp. 540--551.
Další časopisecká literatura dle potřeby.
Recommended resources
M. Sipser. Introduction to the Theory of Computation, 2nd Ed., Thomson, Boston, MA, 2006.
O. Reingold. Undirected connectivity in log-space, J. ACM 55, no. 4 (2008), 17:1--17:24.
S. Datta a G. Prakriya. Planarity testing revisited, in: Proc. 8th annual conference on Theory and Applications of Models of Computation, TAMC'11, Springer, Berlin, 2011, pp. 540--551.
