NP vyhledávací problémy a redukce mezi nimi
| Název práce v češtině: | NP vyhledávací problémy a redukce mezi nimi |
|---|---|
| Název v anglickém jazyce: | NP search problems a reductions among them |
| Klíčová slova: | NP vyhledávací problém, redukce, Modulo-p počítací princip, vyhledávací strom, Nullstellensatz |
| Klíčová slova anglicky: | NP search problem, reduction, Modulo-p counting principle, search tree, Nullstellensatz |
| Akademický rok vypsání: | 2010/2011 |
| Typ práce: | diplomová 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í: | 14.10.2010 |
| Datum zadání: | 14.10.2010 |
| Datum a čas obhajoby: | 25.05.2012 00:00 |
| Datum odevzdání elektronické podoby: | 17.04.2012 |
| Datum odevzdání tištěné podoby: | 10.04.2012 |
| Datum proběhlé obhajoby: | 25.05.2012 |
| Oponenti: | prof. RNDr. Pavel Pudlák, DrSc. |
| Zásady pro vypracování |
| Najít nové redukce mezi NP vyhledávacími problémy ci nové příklady takových problémů.
|
| Seznam odborné literatury |
| P.Beame, S.Cook, J.Edmonds, R.Impagliazzo, T.Pitassi,
The relative complexity of NP search problems, in Proc.of the twenty-seventh annual ACM symposium on Theory of computing table of contents, Las Vegas, Nevada, (1995), 303 - 314. M. Chiari, J.Krajicek, Witnessing functions in bounded arithmetic and search problems, J. of Symbolic Logic, 63(3), (1998), pp. 1095-1115. C. Papadimitriou, The Complexity of the Parity Argument and Other Inefficient proofs of Existence, Journal of Computer and System Sciences archive, Volume 48 , Issue 3 (June 1994). Další literatura viz www.karlin.mff.cuni.cz/~krajicek/liter10b.html . |
| Předběžná náplň práce |
| Je známo několik typů kombinatorických NP vyhledávacích problémů
na něž lze redukovat mnoho jíných takových problémů. Cílem práce je najít nové redukce či nové typy úloh. |
| Předběžná náplň práce v anglickém jazyce |
| A few types of combinatorial NP search problems are known to which it
is possible to reduce many other such problems. The goal of the project is to find new reductions or new types of search problems. |