Název:
Problém spektra
Překlad názvu:
Spectrum problem
Autoři:
Krejčí, Markéta ; Krajíček, Jan (vedoucí práce) ; Kompatscher, Michael (oponent) Typ dokumentu: Bakalářské práce
Rok:
2023
Jazyk:
eng
Abstrakt: [eng][cze] In this thesis we present the notion of a spectrum of a first-order sentence, including several theorems linking it to computational complexity theory and well-known open problems of Scholz and Asser. We show that there are some interesting subsets of N+ that form a spectrum - either by a direct construction or by applying more advanced theorems. Finally, we prove that spectra are closed under union, intersection, addition and multiplication. 1V této práci prezentujeme pojem spektra sentence logiky prvního řádu včetně nekolika vět spojujících ho s teorií složitosti a dvou známých otevřených problémů Scholze a Assera. Ukážeme, že jsou některé zajimavé podmnožiny N+ , které tvoří spektrum - buď přímou kontrukcí nebo za použití pokročilejších vět. Nakonec dokážeme, že spektra jsou uzavřená na sjednocení, průnik, sčítání a násobení. 1
Klíčová slova:
logika prvního řádu|problém spektra|nedeterministický čas; first-order logic|spectrum problem|non-deterministic time