Spectrum problem
Název práce v češtině: | Problém spektra |
---|---|
Název v anglickém jazyce: | Spectrum problem |
Klíčová slova: | logika prvního řádu|problém spektra|nedeterministický čas |
Klíčová slova anglicky: | first-order logic|spectrum problem|non-deterministic time |
Akademický rok vypsání: | 2022/2023 |
Typ práce: | bakalářská práce |
Jazyk práce: | angličtina |
Ústav: | Katedra algebry (32-KA) |
Vedoucí / školitel: | prof. RNDr. Jan Krajíček, DrSc. |
Řešitel: | Bc. Gabriel Krejčí - zadáno a potvrzeno stud. odd. |
Datum přihlášení: | 07.11.2022 |
Datum zadání: | 08.11.2022 |
Datum potvrzení stud. oddělením: | 29.11.2022 |
Datum a čas obhajoby: | 04.09.2023 10:00 |
Datum odevzdání elektronické podoby: | 20.07.2023 |
Datum odevzdání tištěné podoby: | 24.07.2023 |
Datum proběhlé obhajoby: | 04.09.2023 |
Oponenti: | Michael Kompatscher, Ph.D. |
Zásady pro vypracování |
Nastudovat a presentovat definici spektra uzavřené formule 1. řádu a souvislost těchto spekter s třídou výpočetní složitosti NE. Najít příklady zajímavých množin přirozených čísel, která jsou spektra.
Learn and present the definition of a spectrum of a first-order sentence and a connection of spectra to the class of computational complexity NE. Find examples of interesting sets of natural numbers which are spectra. |
Seznam odborné literatury |
A. Durand, N.D. Jones, J.A. Makowsky and M. More,
Fifty Years of the Spectrum Problem: Survey and New Results, preprint (submitted to the Bulletin of Symbolic Logic), 2009 http://www.diku.dk/hjemmesider/ansatte/neil/SpectraSubmitted.pdf R.Fagin, Finite-model theory - a personal perspective, Th.Comp.Sci, 116, (1993), 3-31. |
Předběžná náplň práce |
Problém spektra z teorie konečných modelů je jeden z nejstarších problémů
blízkých slavnému novodobému P vs. NP problému. |
Předběžná náplň práce v anglickém jazyce |
The spectrum problem from finite model theory is one of the oldest
problems close to the famous contemporary P versus NP problem. |