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. 1 V 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

Instituce: Fakulty UK (VŠKP) (web)
Informace o dostupnosti dokumentu: Dostupné v digitálním repozitáři UK.
Původní záznam: http://hdl.handle.net/20.500.11956/183863

Trvalý odkaz NUŠL: http://www.nusl.cz/ntk/nusl-534494


Záznam je zařazen do těchto sbírek:
Školství > Veřejné vysoké školy > Univerzita Karlova > Fakulty UK (VŠKP)
Vysokoškolské kvalifikační práce > Bakalářské práce