NP-snadné - NP-easy - Wikipedia

v teorie složitosti, třída složitosti NP-snadné je sada funkční problémy které jsou řešitelné v polynomiální čas podle a deterministický Turingův stroj s věštec pro některé rozhodovací problém v NP.

Jinými slovy, problém X je NP snadný kdyby a jen kdyby v NP existuje nějaký problém Y takový, že X je polynomial-time Turing redukovatelný Y.^[1] To znamená, že vzhledem k věštec pro Y existuje algoritmus, který řeší X v polynomiálním čase (možná opakovaným používáním tohoto věštce).

NP-easy je jiný název pro FP^NP (viz funkční problém článek) nebo pro FΔ₂P (viz polynomiální hierarchie článek).

Příkladem NP-easy problému je problém seřadit seznam řetězců. Rozhodovací problém „je řetězec A větší než řetězec B“ je v NP. Existují algoritmy jako např quicksort který může seznam seřadit pouze pomocí polynomiálního počtu volání srovnávací rutiny a polynomického množství další práce. Proto je třídění NP-snadné.

Existují také obtížnější problémy, které jsou NP snadné. Vidět NP-ekvivalent například.

Definice NP-easy používá spíše Turingovu redukci než a mnoho-jedna redukce protože odpovědi na problém Y jsou pouze PRAVDA nebo NEPRAVDA, ale odpovědi na problém X může být obecnější. Proto neexistuje žádný obecný způsob, jak přeložit instanci X na instanci Y se stejnou odpovědí.

Poznámky

Reference

• Garey, Michael R.; Johnson, David S. (1979), Počítače a neodolatelnost: Průvodce po teorii NP-úplnosti, W. H. Freeman, ISBN  0-7167-1045-5.