Témata prací (Výběr práce)Témata prací (Výběr práce)(verze: 290)
Detail práce
   Přihlásit přes CAS
Problém spektra
Název práce v češtině: Problém spektra
Název v anglickém jazyce: Spectrum problem
Klíčová slova: Scholzův problém, spektrum, Asserův problém, zobecněné spektrum
Klíčová slova anglicky: Scholz's problem, spectrum, Asser's problem, generalized spectrum
Akademický rok vypsání: 2018/2019
Typ práce: bakalářská práce
Jazyk práce:
Ústav: Katedra algebry (32-KA)
Vedoucí / školitel: prof. RNDr. Jan Krajíček, DrSc.
Řešitel:
Zásady pro vypracování
Nastudovat a presentovat definici spektra uzavřené formule 1. řádu a souvislost těchto spekter s množinami z třídy výpočetní složitosti NE. Najít příklady zajímavých množin přirozených čísel, která jsou spektra.
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