Název: NP vyhledávací problémy
Překlad názvu: NP vyhledávací problémy
Autoři: Jirotka, Tomáš ; Krajíček, Jan (vedoucí práce) ; Pudlák, Pavel (oponent)
Typ dokumentu: Diplomové práce
Rok: 2011
Jazyk: eng
Abstrakt: [eng] [cze]
Title: NP search problems Author: Tomáš Jirotka Department: Department of Algebra Supervisor: Prof. RNDr. Jan Krajíček, DrSc. Abstract: The thesis summarizes known results in the field of NP search pro- blems. We discuss the complexity of integer factoring in detail, and we propose new results which place the problem in known classes and aim to separate it from PLS in some sense. Furthermore, we define several new search problems. Keywords: Computational complexity, TFNP, integer factorization. 1 Název práce: NP vyhledávací problémy Autor: Tomáš Jirotka Katedra: Katedra algebry Vedoucí diplomové práce: Prof. RNDr. Jan Krajíček, DrSc. Abstrakt: Práce shrnuje dosavadní výsledky v oblasti NP vyhledávacích problémů. Podrobně diskutujeme otázku složitosti faktorizace celých čísel a před- kládáme výsledky, které zařazují tento problém do již známých složitostních tříd a v jistém smyslu se jej snaží separovat z PLS. Dále definujeme několik nových vyhledávacích problémů. Klíčová slova: Výpočetní složitost, TFNP, faktorizace čísel.
Klíčová slova: faktorizace čísel; TFNP; Výpočetní složitost; Computational complexity; integer factorization; TFNP

Instituce: Fakulty UK (VŠKP) (web)
Informace o dostupnosti dokumentu: Dostupné v digitálním repozitáři UK.
Původní záznam: http://hdl.handle.net/20.500.11956/35982

Trvalý odkaz NUŠL: http://www.nusl.cz/ntk/nusl-300252


Záznam je zařazen do těchto sbírek:
Školství > Veřejné vysoké školy > Univerzita Karlova > Fakulty UK (VŠKP)
Vysokoškolské kvalifikační práce > Diplomové práce