Funkció probléma - Function problem

A számítási komplexitás elméletében a függvényprobléma olyan számítási probléma, ahol minden bemenetre egyetlen kimenet (egy teljes függvény ) várható, de a kimenet összetettebb, mint egy döntési probléma . Funkciós problémák esetén a kimenet nem egyszerűen „igen” vagy „nem”.

Formális meghatározás

A funkcionális probléma definíció szerint egy kapcsolat több mint húrok egy tetszőleges ábécé : ${\ displaystyle P}$${\ displaystyle R}$ ${\ displaystyle \ Sigma}$

${\ displaystyle R \ subseteq \ Sigma ^{*} \ times \ Sigma ^{*}}$

Egy algoritmus megoldja, ha minden olyan bemenetre , amely kielégítő létezik , az algoritmus előállít egyet . ${\ displaystyle P}$${\ displaystyle x}$${\ displaystyle y}$${\ displaystyle (x, y) \ in R}$${\ displaystyle y}$

Példák

Jól ismert függvényproblémát ad a Functional Boolean Satisfiability Problem, röviden FSAT . A SAT döntési problémához szorosan kapcsolódó probléma a következőképpen fogalmazható meg:

Ha egy változókkal rendelkező logikai képletet kap , keressen olyan hozzárendelést , amely kiértékeli vagy eldönti, hogy ilyen hozzárendelés nem létezik.${\ displaystyle \ varphi}$${\ displaystyle x_ {1}, \ ldots, x_ {n}}$${\ displaystyle x_ {i} \ rightarrow \ {{\ text {TRUE}}, {\ text {FALSE}} \}}$${\ displaystyle \ varphi}$${\ displaystyle {\ text {TRUE}}}$

Ebben az esetben a relációt megfelelően kódolt logikai képletek és a kielégítő hozzárendelések adják meg. Míg egy SAT algoritmussal, amelyet egy képlettel táplálnak , csak "nem kielégítõ" vagy "kielégítõ" értéket kell visszaadnia, az FSAT algoritmusnak valamilyen kielégítõ hozzárendelést kell visszaadnia az utóbbi esetben. ${\ displaystyle R}$${\ displaystyle \ varphi}$

További figyelemre méltó példák az utazó eladó problémája , amely az eladó által választott útvonalat kéri, valamint az egész faktorálási probléma , amely a tényezők listáját kéri.

Kapcsolat más bonyolultsági osztályokkal

Tekintsünk egy tetszőleges döntési problémát az NP osztályban . Az NP definíciója szerint minden, igennel válaszolt problémapéldány rendelkezik polinom méretű tanúsítvánnyal, amely bizonyítékul szolgál az „igen” válaszra. A készletet tehát ezen sorok képez kapcsolatban, ami a függvény probléma „adott az , talál egy igazolást az ”. Ez a funkció a probléma az úgynevezett a funkciója változata a ; az FNP osztályba tartozik . ${\ displaystyle L}$${\ displaystyle x}$${\ displaystyle y}$${\ displaystyle (x, y)}$${\ displaystyle x}$${\ displaystyle L}$${\ displaystyle y}$${\ displaystyle x}$${\ displaystyle L}$

FNP lehet elképzelni, mint a függvény osztály analóg NP , hogy megoldásai FNP problémák hatékonyan lehet (azaz a polinomiális szempontjából az a bemenet hosszát) igazolt , de nem feltétlenül hatékonyan talált . Ezzel szemben az FP osztály , amely a P függvényosztály analógjának tekinthető , olyan függvényfeladatokból áll, amelyek megoldása polinomiális időben megtalálható.

Önredukálhatóság

Figyeld meg, hogy a fent bemutatott FSAT probléma csak polinomiálisan sok hívással oldható meg egy alprogramhoz, amely eldönti a SAT problémát: Egy algoritmus először megkérdezheti, hogy a képlet kielégíthető -e . Ezt követően az algoritmus a TRUE változót rögzítheti , és újra megkérdezheti. Ha a kapott képlet továbbra is kielégíthető, az algoritmus továbbra is az IGAZ értéket rögzíti , és továbbra is javítja , ellenkező esetben úgy dönt, hogy hamisnak kell lennie, és folytatja. Így az FSAT polinomidőben megoldható egy Oracle döntő SAT segítségével . Általában a probléma NP nevezik self-redukálható , ha függvénye variáns lehet polinomiális időben megoldható segítségével egy orákulum döntés az eredeti probléma. Minden NP-teljes probléma önmagában csökkenthető. Feltételezhető, hogy az egész faktorálási probléma nem önredukálható. ${\ displaystyle \ varphi}$${\ displaystyle x_ {1}}$${\ displaystyle x_ {1}}$${\ displaystyle x_ {2}}$${\ displaystyle x_ {1}}$

Csökkentések és teljes problémák

Funkció problémákat lehet csökkenteni hasonlóan döntési problémák: Mivel működési problémákat , és azt mondjuk, hogy csökkenti az , ha létezik polinomiális idejű kiszámítható függvényt , és úgy, hogy minden esetben a és a lehetséges megoldásokat a fennáll az, hogy ${\ displaystyle \ Pi _ {R}}$${\ displaystyle \ Pi _ {S}}$${\ displaystyle \ Pi _ {R}}$${\ displaystyle \ Pi _ {S}}$${\ displaystyle f}$${\ displaystyle g}$${\ displaystyle x}$${\ displaystyle R}$${\ displaystyle y}$${\ displaystyle S}$

• Ha van -megoldása, akkor van -megoldása.${\ displaystyle x}$${\ displaystyle R}$${\ displaystyle f (x)}$${\ displaystyle S}$
• ${\ displaystyle (f (x), y) \ in S \ azt jelenti (x, g (x, y)) \ R. -ben}$

Ezért lehetséges az FNP-komplett problémák meghatározása az NP-teljes problémához hasonlóan:

A probléma akkor teljes, ha az FNP minden problémája csökkenthető . A komplexitás osztálya FNP-teljes problémák jelöljük FNPC vagy FNPC . Ezért az FSAT probléma az FNP teljes problémája is, és azt tartja, hogy akkor és csak akkor . ${\ displaystyle \ Pi _ {R}}$${\ displaystyle \ Pi _ {R}}$${\ displaystyle \ mathbf {P} = \ mathbf {NP}}$${\ displaystyle \ mathbf {FP} = \ mathbf {FNP}}$

Teljes működési problémák

Az összefüggés meghatározására használt, működési problémákat az a hátránya, hogy hiányos: Nem minden bemenet van egy párja , hogy . Ezért a bizonyítékok kiszámíthatóságának kérdése nem választható el létezésük kérdésétől. Ennek a problémának a kiküszöbölésére célszerű úgy tekinteni, hogy a függvényfeladatok a teljes kapcsolatokra korlátozódnak, így az TFNP osztály az FNP alosztálya . Ez az osztály olyan problémákat tartalmaz, mint a tiszta Nash -egyensúlyok kiszámítása bizonyos stratégiai játékokban, ahol garantáltan létezik megoldás. Ezenkívül, ha a TFNP tartalmaz bármilyen FNP-teljes problémát, akkor ez következik . ${\ displaystyle R (x, y)}$${\ displaystyle x}$${\ displaystyle y}$${\ displaystyle (x, y) \ in R}$${\ displaystyle \ mathbf {NP} = {\ textbf {co-NP}}}$

Lásd még

• Döntési probléma
• Keresési probléma
• Számlálási probléma (bonyolultság)
• Optimalizálási probléma

Hivatkozások