Problém spektra
| Thesis title in Czech: | Problém spektra |
|---|---|
| Thesis title in English: | Spectrum problem |
| Key words: | Scholzův problém, spektrum, Asserův problém, zobecněné spektrum |
| English key words: | Scholz's problem, spectrum, Asser's problem, generalized spectrum |
| Academic year of topic announcement: | 2009/2010 |
| Thesis type: | Bachelor's thesis |
| Thesis language: | čeština |
| Department: | Department of Algebra (32-KA) |
| Supervisor: | prof. RNDr. Jan Krajíček, DrSc. |
| Author: | Mgr. Kristýna Poláková - assigned and confirmed by the Study Dept. |
| Date of registration: | 02.11.2009 |
| Date of assignment: | 24.11.2009 |
| Date and time of defence: | 22.06.2011 00:00 |
| Date of electronic submission: | 27.05.2011 |
| Date of submission of printed version: | 27.05.2011 |
| Date of proceeded defence: | 22.06.2011 |
| Opponents: | Mgr. et Mgr. Emil Jeřábek, Dr., Ph.D. |
| Guidelines |
| 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. |
| References |
| 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. |
| Preliminary scope of work |
| 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. |
| Preliminary scope of work in English |
| The spectrum problem from finite model theory is one of the oldest
problems close to the famous contemporary P versus NP problem. |