Original title: NP vyhledávací problémy
Translated title: NP vyhledávací problémy
Authors: Jirotka, Tomáš ; Krajíček, Jan (advisor) ; Pudlák, Pavel (referee)
Document type: Master’s theses
Year: 2011
Language: eng
Abstract: [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.
Keywords: Computational complexity; integer factorization; TFNP; faktorizace čísel; TFNP; Výpočetní složitost

Institution: Charles University Faculties (theses) (web)
Document availability information: Available in the Charles University Digital Repository.
Original record: http://hdl.handle.net/20.500.11956/35982

Permalink: http://www.nusl.cz/ntk/nusl-300252


The record appears in these collections:
Universities and colleges > Public universities > Charles University > Charles University Faculties (theses)
Academic theses (ETDs) > Master’s theses