Témata prací (Výběr práce)Témata prací (Výběr práce)(verze: 368)
Detail práce
   Přihlásit přes CAS
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.
 
Univerzita Karlova | Informační systém UK