Procházet otázky :: SZZ na MFF UK

#

- Hlavní strana
- Okruhy
- Projít
- Stáhnout
- Co je potřeba
- Chci přispět
- Kredity

Hledat:

## Prohlížení státnicových textů

## Třídy složitosti P a NP, převoditelnost, NP-úplnost

TODO: doplnit, tohle asi nestaci na pohodovou zkousku (aspon podle toho co jsem vnimal, jsa svedek zkouseni u Dr. Yaghoba) - chce to napr. nejaky priklad prevedeni jako delal Kucera, mozna jeste neco

Definice

- Úloha - Pro dané zadání (vstup, instanci úlohy) najít výstup s danými vlastnostmi.
- Optimalizační úloha - Pro dané zadání najít optimální (většinou nejmenší nebo největší) výstup s danými vlastnostmi.
- Rozhodovací problém - Pro dané zadání odpovědět ANO/NE.

Definice (třída P)

Třídu složitosti P (někdy též PTIME) tvoří problémy řešitelné sekvenčními deterministickými algoritmy v polynomiálním čase, tj. jejich časová složitost je . O algoritmech ve třídě P také říkáme, že jsou efektivně řešitelné.

Definice (třída NP)

Třída NP (NPTIME) je třída problémů řešitelných v polynomiálním čase sekvenčními nedeterministickými algoritmy.

Poznámka

Ví se, že . Neví se však, zda . Předpokládá se to, ale ještě to nikdo nedokázal.

Příklady problémů ze třídy NP

- KLIKA(úplný podgraf) - Je dán neorientovaný graf a číslo . Existuje v úplný podgraf velikosti aspoň ?
- HK(Hamiltonovská kružnice) - Je dán neorientovaný graf . Existuje v Hamiltonovská kružnice?
- SP(Součet podmnožiny) - Jsou dána přirozená čísla . Existuje podmnožina čísel , jejíž součet je přesně ?

Definice (převody mezi rozhodovacími problémy)

Nechť , jsou dva rozhodovací problémy. Říkáme, že je polynomiálně redukovatelný (převoditelný) na , pokud existuje zobrazení z množiny zadání problému do množiny zadání problému s následujícími vlastnostmi:

- Nechť je zadání problému a zadání problému , takové, že . Potom je kladné zadání problému právě tehdy, když je kladné zadání problému .
- Nechť je zadání problému . Potom je zadání problému (deterministicky sekvenčně) zkonstruovatelné v polynomiálním čase vzhledem k velikosti .

Definice (NP-těžký problém)

Problém je NP-těžký, pokud pro libovolný problém ze třídy NP platí, že je polynomiálně redukovatelný na .

Definice (NP-úplný problém)

Problém je NP-úplný, pokud patří do třídy NP a je NP-těžký.

Důsledky

- Pokud je NP-těžký a navíc je polynomiálně redukovatelný na , tak je taky NP-těžký.
- Pokud existuje polynomiální algoritmus pro nějaký NP-těžký problém, pak existují polynomiální algoritmy pro všechny problémy ve třídě NP.

Věta (Cook-Levin 1971)

Existuje NP-úplný problém. (Dokázáno pro SAT)