Spectrum problem

• 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, Cobhamova věta
• Klíčová slova anglicky: Scholz's problem, spectrum, Asser's problem, generalized spectrum, Cobham's theorem
• Akademický rok vypsání: 2019/2020
• 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: skrytý - zadáno a potvrzeno stud. odd.
• Datum přihlášení: 21.10.2019
• Datum zadání: 21.10.2019
• Datum potvrzení stud. oddělením: 21.11.2019
• Datum a čas obhajoby: 29.06.2020 10:00
• Datum odevzdání elektronické podoby: 02.06.2020
• Datum odevzdání tištěné podoby: 04.06.2020
• Datum proběhlé obhajoby: 29.06.2020
• Oponenti: doc. Mgr. Jan Šaroch, Ph.D.

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.