SNP (složitost) - SNP (complexity) - Wikipedia

v teorie výpočetní složitosti, SNP (z Přísné NP) je třída složitosti obsahující omezenou podmnožinu NP na základě jeho logické charakterizace z hlediska graficko-teoretický vlastnosti. Tvoří základ pro definici třídy MaxSNP z optimalizační problémy.

Je definována jako třída problémů, které jsou vlastnostmi relační struktury (jako grafy ) vyjádřitelný a logika druhého řádu vzorec v následujícím tvaru:

{ displaystyle existuje S_ {1} tečky existuje S _ { ell} , forall v_ {1} dots forall v_ {m} , phi (R_ {1}, dots, R_ {k }, S_ {1}, dots, S _ { ell}, v_ {1}, dots, v_ {m})}

,

kde ${ displaystyle R_ {1}, tečky, R_ {k}}$ jsou vztahy struktury (například vztah sousednosti pro graf), ${ displaystyle S_ {1}, tečky, S _ { ell}}$ jsou neznámé vztahy (sady n-tic vrcholů) a ${ displaystyle phi}$ je vzorec bez kvantifikátoru: jakákoli booleovská kombinace vztahů.^[1] To znamená, že je povolena pouze existenční kvantifikace druhého řádu (přes vztahy) a je povolena pouze univerzální kvantifikace prvního řádu (přes vrcholy). Pokud by byla také povolena existenční kvantifikace přes vrcholy, výsledná třída složitosti by se rovnala NP (přesněji , třída těch vlastností relačních struktur, které jsou v NP), skutečnost známá jako Faginova věta.

Například SNP obsahuje 3-Coloring (problém určení, zda daný graf je 3 barvy ), protože to lze vyjádřit následujícím vzorcem:

{ displaystyle existuje S_ {1} existuje S_ {2} existuje S_ {3} , forall u forall v , { bigl (} S_ {1} (u) vee S_ {2} ( u) vee S_ {3} (u) { bigr)} , wedge , { bigl (} E (u, v) , implies , ( neg S_ {1} (u) vee neg S_ {1} (v)) , wedge , left ( neg S_ {2} (u) vee neg S_ {2} (v) right) , wedge , ( neg S_ {3} (u) vee neg S_ {3} (v)) { bigr)}}

.

Tady ${ displaystyle E}$ označuje vztah sousednosti vstupního grafu, zatímco množiny (unární vztahy) ${ displaystyle S_ {1}, S_ {2}, S_ {3}}$ odpovídají sadám vrcholů zabarvených jednou ze 3 barev. Podobně SNP obsahuje k-SAT problém: booleovský problém uspokojivosti (SAT), kde je vzorec omezen na konjunktivní normální forma a maximálně k literály na klauzuli, kde k je opraveno.

MaxSNP

Analogická definice uvažuje optimalizační problémy, když místo požadavku na vzorec, který má být uspokojen Všechno n-tic, člověk chce maximalizovat počet n-tic, pro které je spokojen. To znamená, MaxSNP₀ je definována jako třída optimalizačních problémů na relačních strukturách vyjádřitelná v následující podobě:

{ displaystyle max limity _ {S_ {1}, tečky, S _ { ell}} | {(v_ {1}, dots, v_ {m}) colon phi (R_ {1}, dots, R_ {k}, S_ {1}, dots, S _ { ell}, v_ {1}, dots, v_ {m}) } |}

MaxSNP je pak definována jako třída všech problémů s L-redukce (lineární redukce, ne zmenšení log prostoru) k problémům v MaxSNP₀.^[2]Například, MAX-3SAT je problém v MaxSNP₀: daný případ 3-CNF-SAT ( booleovský problém uspokojivosti se vzorcem v konjunktivní normální forma a maximálně 3 literály na klauzuli), najděte úkol splňující co nejvíce klauzulí. Ve skutečnosti je to přirozené kompletní problém pro MaxSNP.

Existuje pevný poměr aproximační algoritmus vyřešit jakýkoli problém v MaxSNP, proto MaxSNP je obsažen v APX, třída všech problémů přibližně v nějakém konstantním poměru. Ve skutečnosti uzavření MaxSNP pod Snížení PTAS (o něco obecnější než L-redukce) se rovná APX; to znamená každý problém v APX má Snížení PTAS na to z nějakého problému v MaxSNPZejména každý MaxSNP-kompletní problém (pod L-redukcemi nebo pod AP-redukce ) je také APX-kompletní (v rámci redukcí PTAS), a proto nepřijímá PTAS, pokud P = NP. Důkaz toho však spoléhá na Věta o PCP, zatímco důkazy o MaxSNP- úplnost je často elementární.

Viz také

APX

Reference

^ Feder, Tomás; Vardi, Moshe Y. (1993). "Monotónní monadické SNP a omezení spokojenosti". Sborník z dvacátého pátého symposia ACM o teorii práce s počítačem. doi:10.1145/167088.167245.
^ Papadimitriou, Christos H .; Yannakakis, Mihalis (1991). "Třídy optimalizace, aproximace a složitosti". J. Comput. Syst. Sci. 43 (3): 425–440. Zbl 0765.68036.

Grädel, Erich; Kolaitis, Phokion G .; Libkin, Leonid; Maarten, Marx; Spencer, Joel; Vardi, Moshe Y.; Venema, Yde; Weinstein, Scott (2007). Teorie konečných modelů a její aplikace. Texty v teoretické informatice. Řada EATCS. Berlín: Springer-Verlag. p.350. ISBN 978-3-540-00428-8. Zbl 1133.03001.

externí odkazy

[1] Feder, Tomás; Vardi, Moshe Y. (1993). "Monotónní monadické SNP a omezení spokojenosti". Sborník z dvacátého pátého symposia ACM o teorii práce s počítačem. doi:10.1145/167088.167245.

[2] Papadimitriou, Christos H .; Yannakakis, Mihalis (1991). "Třídy optimalizace, aproximace a složitosti". J. Comput. Syst. Sci. 43 (3): 425–440. Zbl 0765.68036.

[1]

[2]