NP vyhledávací problémy
| Thesis title in Czech: | NP vyhledávací problémy |
|---|---|
| Thesis title in English: | NP search problems |
| Key words: | Výpočetní složitost, TFNP, faktorizace čísel. |
| English key words: | Computational complexity, TFNP, integer factorization. |
| Academic year of topic announcement: | 2009/2010 |
| 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: | 12.11.2009 |
| Date of assignment: | 12.11.2009 |
| Date and time of defence: | 19.05.2011 00:00 |
| Date of electronic submission: | 13.04.2011 |
| Date of submission of printed version: | 15.04.2011 |
| Date of proceeded defence: | 19.05.2011 |
| Opponents: | prof. RNDr. Pavel Pudlák, DrSc. |
| Guidelines |
| Najít nové redukce mezi NP vzhledá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. 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). |
| 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 další podobné 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 other similar reductions or new types of search problems. |