Parametrizovaná složitost - Parameterized complexity

V informatice je parametrizovaná složitost odvětví teorie výpočetní složitosti, které se zaměřuje na klasifikaci výpočetních problémů podle jejich inherentní obtížnosti s ohledem na více parametrů vstupu nebo výstupu. Složitost problému se poté měří jako funkce těchto parametrů. To umožňuje klasifikaci NP-tvrdých problémů v jemnějším měřítku než v klasickém prostředí, kde se složitost problému měří pouze jako funkce počtu bitů na vstupu. První systematickou práci na parametrizované složitosti provedli Downey & Fellows (1999) .

Za předpokladu, že P ≠ NP , existuje mnoho přirozených problémů, které vyžadují superpolynomiální dobu běhu, když je složitost měřena pouze z hlediska velikosti vstupu, ale které lze vypočítat v čase, který je polynomem ve velikosti vstupu a exponenciálním nebo horším v parametr k . Pokud je tedy k stanoveno na malou hodnotu a růst funkce nad k je relativně malý, lze tyto problémy stále považovat za „zvládnutelné“ navzdory jejich tradiční klasifikaci jako „neřešitelné“.

Existence efektivních, přesných a deterministických algoritmů řešení pro NP-úplné nebo jinak NP-tvrdé problémy je považována za nepravděpodobnou, pokud vstupní parametry nejsou pevné; všechny známé algoritmy řešení těchto problémů vyžadují čas, který je exponenciální (nebo alespoň superpolynomický) v celkové velikosti vstupu. Některé problémy však lze vyřešit pomocí algoritmů, které jsou exponenciální pouze ve velikosti fixního parametru, zatímco polynom ve velikosti vstupu. Takový algoritmus se nazývá algoritmustrableable (fpt-) s pevným parametrem , protože problém lze efektivně vyřešit pro malé hodnoty pevného parametru.

Problémy, ve kterých je opraven některý parametr k, se nazývají parametrizované problémy. O parametrizovaném problému, který umožňuje takový algoritmus fpt, ​​se říká, že je to problém s fixními parametry a patří do třídy FPT , a rané jméno teorie parametrizované složitosti byla traktabilita s pevnými parametry .

Mnoho problémů má následující podobu: má-li objekt x a nezáporné celé číslo k , má x nějakou vlastnost, která závisí na k ? Například pro problém s vrcholovým krytem může být parametrem počet vrcholů v krytu. V mnoha aplikacích, například při modelování korekce chyb, lze předpokládat, že parametr bude ve srovnání s celkovou velikostí vstupu „malý“. Pak je náročné najít algoritmus, který je exponenciální pouze v k , a ne ve vstupní velikosti.

Tímto způsobem lze parametrizovanou složitost vnímat jako dvourozměrnou teorii složitosti. Tento koncept je formován takto:

Parametrizované problémem je jazyk , kde je konečná abeceda. Druhá složka se nazývá parametr problému.
Parametrizovaný problém L je fixovatelný, pokud je otázka „ ?“ lze rozhodnout za běhu , kde f je libovolná funkce závislá pouze na k . Odpovídající třída složitosti se nazývá FPT .

Například existuje algoritmus, který řeší problém krytí vrcholu v čase, kde n je počet vrcholů a k je velikost krytu vrcholu. To znamená, že vrcholový kryt je fixovatelný s možností řešení s velikostí řešení jako parametrem.

Třídy složitosti

FPT

FPT obsahuje pevné parametry , které lze vyřešit, což jsou problémy, které lze vyřešit včas pro nějakou vypočítatelnou funkci f . Obvykle se o této funkci uvažuje jako o jedné exponenciální, jako například, ale definice připouští funkce, které rostou ještě rychleji. To je zásadní pro velkou část rané historie této třídy. Rozhodující součástí definice je vyloučit funkce formuláře , jako např . Třída FPL (fixed parameter linear) je třída problémů řešitelných v čase pro nějakou vypočítatelnou funkci f . FPL je tedy podtřídou FPT.

Příkladem je problém uspokojivosti , parametrizovaný počtem proměnných. Daný vzorec velikosti m s proměnnými k lze zkontrolovat hrubou silou v čase . Vrchol krytu o rozměrech k v grafu řádu n lze nalézt v čase , takže tento problém je také v FPT.

Příkladem problému, o kterém se předpokládá, že není v FPT, je zbarvení grafu parametrizované počtem barev. Je známo, že 3-zbarvení je NP-tvrdé a algoritmus pro graf k -barvení v čase pro by běžel v polynomiálním čase ve velikosti vstupu. Pokud tedy zbarvení grafu parametrizované počtem barev bylo v FPT, pak P = NP .

Existuje řada alternativních definic FPT. Například požadavek na provozní dobu lze nahradit . Parametrizovaný problém je také v FPT, pokud má takzvané jádro. Kernelizace je technika předzpracování, která redukuje původní instanci na její „tvrdé jádro“, což je možná mnohem menší instance, která je ekvivalentní původní instanci, ale má velikost, která je omezena funkcí v parametru.

FPT je uzavřen pod parametrizovanou redukcí zvanou fpt-reduction , která současně zachovává velikost instance a parametr.

Je zřejmé, že FPT obsahuje všechny vypočítatelné problémy v polynomiálním čase. Kromě toho obsahuje všechny optimalizační problémy v NP, které umožňují efektivní schéma aproximace v polynomiálním čase (EPTAS) .

W hierarchie

W hierarchie je kolekce počítačových tříd složitosti. Parametrizovaný problém je ve třídě W [ i ], pokud lze každou instanci transformovat (v čase fpt-time) na kombinatorický obvod, který má útku maximálně i , takže právě tehdy, když existuje uspokojivé přiřazení vstupům, které přiřadí 1 přesně k vstupům. Útek je největší počet logických jednotek s neomezeným fan-inem na jakékoli cestě od vstupu k výstupu. Celkový počet logických jednotek na cestách (označovaných jako hloubka) musí být omezen konstantou, která platí pro všechny instance problému.

Všimněte si, že a pro všechny . Třídy v hierarchii W jsou také uzavřeny pod fpt-redukcí.

Mnoho přirozených výpočetních problémů zaujímá nižší úrovně, W [1] a W [2].

W [1]

Mezi příklady W [1] -kompletních problémů patří

  • rozhodování, zda daný graf obsahuje kliku o velikosti k
  • rozhodování, zda daný graf obsahuje nezávislou množinu velikosti k
  • rozhodování o tom, zda daný nedeterministický jednopáskový Turingův stroj přijímá v k krocích (problém s „krátkým přijetím Turingova stroje“). To platí také pro nedeterministické Turingovy stroje s páskami f ( k ) a dokonce i f ( k ) s f ( k ) -rozměrnými páskami, ale i s tímto rozšířením je omezení velikosti abecedy pásky f ( k ) fixovatelné s pevným parametrem. Rozhodující je, že větvení Turingova stroje v každém kroku může záviset na n , velikosti vstupu. Tímto způsobem může Turingův stroj prozkoumat n O ( k ) výpočetních cest.

Z [2]

Mezi příklady W [2] úplných problémů patří

  • rozhodování, zda daný graf obsahuje dominující množinu velikosti k
  • rozhodování, zda daný nedeterministický vícepásmový Turingův stroj přijímá v k krocích (problém s „krátkým vícepásmovým Turingovým strojem“). Rozhodující je, že větvení může záviset na n (jako varianta W [1]), stejně jako počet pásek. Alternativní W [2] -kompletní formulace umožňuje pouze jednopáskové Turingovy stroje, ale velikost abecedy může záviset na n .

W [ t ]

lze definovat pomocí rodiny Weighted Weft- t- Depth- d SAT problems for : is the class of parameterized problems that fpt-redu to this problem, and .

Zde je Weighted Weft- t -Depth- d SAT následující problém:

  • Vstup: Booleovský vzorec hloubky nanejvýš d a útku nanejvýš t a čísla k . Hloubka je maximální počet závor na libovolnou cestu od kořene do listu, a útek je maximální počet závor větvení alespoň ve třech na libovolnou cestu od kořene do listu.
  • Otázka: Má vzorec uspokojivé přiřazení Hammingovy váhy přesně k ?

Je možné ukázat, že pro problém je vážená t- Normalizace SAT kompletní pro fpt-redukce. Zde je vážený t- normalizace SAT následující problém:

  • Vstup: Booleovský vzorec hloubky nanejvýš t, brána AND nahoře a číslo k .
  • Otázka: Má vzorec uspokojivé přiřazení Hammingovy váhy přesně k ?

W [ P ]

W [ P ] je skupina problémů, které mohou být podle rozhodnutí nedeterministického -time Turing stroj, který umožňuje ve většině nedeterministickými možnosti v počítání na (a k -restricted Turingův stroj). Flum & Grohe (2006)

Je známo, že FPT je obsažena ve W [P] a zařazení je považováno za přísné. Vyřešení tohoto problému by však znamenalo řešení problému P versus NP .

Jiná spojení s neparametrickou výpočetní složitostí spočívají v tom, že FPT se rovná W [ P ] tehdy a jen tehdy, pokud je možné včas rozhodnout o uspokojivosti obvodu , nebo zda a pouze tehdy, když existuje vypočítatelná, neklesající, neomezená funkce f tak, že všechny jazyky rozpoznané nedeterministickým polynomem -time Turingův stroj pomocí nedeterministické volby jsou v  P .

W [ P ] lze volně považovat za třídu problémů, kde máme množinu S z položek n a chceme najít podmnožinu velikosti k takovou, aby platila určitá vlastnost. Můžeme zakódovat volbu jako seznam celých čísel k , uložených v binárním formátu . Protože nejvyšší z těchto čísel může být n , jsou pro každé číslo potřeba bity. Proto je pro kódování volby potřeba celkem bitů. Proto můžeme vybrat podmnožinu s nedeterministickými možnostmi.

XP

XP je třída parametrizovaných problémů, které lze vyřešit včas pro nějakou vypočítatelnou funkci f . Tyto problémy se nazývají polynomy slicewise , v tom smyslu, že každý „řez“ pevného k má polynomiální algoritmus, i když možná s jiným exponentem pro každé k. Porovnejte to s FPT, které pouze umožňuje odlišný konstantní prefaktor pro každou hodnotu k. XP obsahuje FPT a je známo, že toto zadržení je přísné diagonalizací.

para-NP

para-NP je třída parametrizovaných problémů, které lze vyřešit nedeterministickým algoritmem v čase pro nějakou vypočítatelnou funkci f . Je známo, že právě tehdy .

Problém je para-NP-hard, pokud je -hard již pro konstantní hodnotu parametru. To znamená, že existuje „plátek“ pevného k, který je -hard. Parametrizovaný problém, který je -hard, nemůže patřit do třídy , pokud . Klasickým příkladem -hard parametrizovaného problému je zbarvení grafu , parametrizované počtem k barev, který je již -hard for (viz Zbarvení grafu # Výpočetní složitost ).

Hierarchie

Hierarchie je kolekce počítačových tříd složitosti podobných W hierarchie. Zatímco je však hierarchie W hierarchií obsaženou v NP, hierarchie A více napodobuje hierarchii polynomiálního času z klasické složitosti. Je známo, že platí A [1] = W [1].

Poznámky

  1. ^ Chen, Kanj a Xia 2006
  2. ^ Grohe (1999)
  3. ^ Buss, Jonathan F, Islam, Tarique (2006). "Zjednodušení hierarchie útku" . Teoretická informatika . 351 (3): 303–313. doi : 10,1016 / j.tcs.2005.10.002 .CS1 maint: více jmen: seznam autorů ( odkaz )
  4. ^ Flum & Grohe , str. 39.

Reference

externí odkazy