Original title: Problém spektra
Translated title: Spectrum problem
Authors: Krejčí, Markéta ; Krajíček, Jan (advisor) ; Kompatscher, Michael (referee)
Document type: Bachelor's theses
Year: 2023
Language: eng
Abstract: [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
Keywords: first-order logic|spectrum problem|non-deterministic time; logika prvního řádu|problém spektra|nedeterministický čas

Institution: Charles University Faculties (theses) (web)
Document availability information: Available in the Charles University Digital Repository.
Original record: http://hdl.handle.net/20.500.11956/183863

Permalink: http://www.nusl.cz/ntk/nusl-534494


The record appears in these collections:
Universities and colleges > Public universities > Charles University > Charles University Faculties (theses)
Academic theses (ETDs) > Bachelor's theses