Abstrakt
Dizertační práce se sestává ze dvou částí. V první části studujeme problémy splnitelnosti omezení nad nekonečnými obory hodnot.
Nejvýznamější výsledek této části je úplná klasifikace složitosti problému splnitelnosti omezení pro jazyky nad hustým lineárním uspořádáním. V druhé části studujeme výpočetní složitost problémů souvisejících s kreslením grafů.