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: | NP vyhledávací problém|redukce |
| Klíčová slova anglicky: | NP search problem|reduction |
| Akademický rok vypsání: | 2021/2022 |
| Typ práce: | diplomová práce |
| Jazyk práce: | |
| Ú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í: | 11.11.2021 |
| Datum zadání: | 11.11.2021 |
| Datum potvrzení stud. oddělením: | 17.12.2021 |
| Zásady pro vypracování |
| Najít nové příklady NP vyhledávacích problémů a studovat existenci jejich redukcí na známé problémy jak jsou
PLS či PPA a další. |
| 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. 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ů 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é typy úloh a studovat jejich redukce na známé problémy. |
| Předběžná náplň práce v anglickém jazyce |
| A few types of 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 types of search problems and study their reductions to known problems. |