NP vyhledávací problémy
| Název práce v češtině: | NP vyhledávací problémy |
|---|---|
| Název v anglickém jazyce: | NP search problems |
| Klíčová slova: | Výpočetní složitost, TFNP, faktorizace čísel. |
| Klíčová slova anglicky: | Computational complexity, TFNP, integer factorization. |
| Akademický rok vypsání: | 2009/2010 |
| 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í: | 12.11.2009 |
| Datum zadání: | 12.11.2009 |
| Datum a čas obhajoby: | 19.05.2011 00:00 |
| Datum odevzdání elektronické podoby: | 13.04.2011 |
| Datum odevzdání tištěné podoby: | 15.04.2011 |
| Datum proběhlé obhajoby: | 19.05.2011 |
| Oponenti: | prof. RNDr. Pavel Pudlák, DrSc. |
| Zásady pro vypracování |
| Najít nové redukce mezi NP vzhledá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. J.Krajíček, Structured pigeonhole principle, search problems and hard tautologies, J.Symbolic Logic, 70(2), 2005, str.619-630. 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). |
| 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 další podobné 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 other similar reductions or new types of search problems. |