NP vyhledávací problémy a redukce mezi nimi
| Thesis title in Czech: | NP vyhledávací problémy a redukce mezi nimi |
|---|---|
| Thesis title in English: | NP search problems a reductions among them |
| Key words: | NP vyhledávací problém, redukce, Modulo-p počítací princip, vyhledávací strom, Nullstellensatz |
| English key words: | NP search problem, reduction, Modulo-p counting principle, search tree, Nullstellensatz |
| Academic year of topic announcement: | 2010/2011 |
| Thesis type: | diploma thesis |
| Thesis language: | angličtina |
| Department: | Department of Algebra (32-KA) |
| Supervisor: | prof. RNDr. Jan Krajíček, DrSc. |
| Author: | hidden - assigned and confirmed by the Study Dept. |
| Date of registration: | 14.10.2010 |
| Date of assignment: | 14.10.2010 |
| Date and time of defence: | 25.05.2012 00:00 |
| Date of electronic submission: | 17.04.2012 |
| Date of submission of printed version: | 10.04.2012 |
| Date of proceeded defence: | 25.05.2012 |
| Opponents: | prof. RNDr. Pavel Pudlák, DrSc. |
| Guidelines |
| Najít nové redukce mezi NP vyhledávacími problémy ci nové příklady takových problémů.
|
| References |
| 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 . |
| Preliminary scope of work |
| 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. |
| Preliminary scope of work in English |
| 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. |