Testování vlastností - Property testing

Ve vědě o počítačích , je vlastnost testování algoritmus pro rozhodovací problém je algoritmus , jehož dotaz složitost na jeho vstup je mnohem menší než velikost instance problému. Algoritmy pro testování vlastností se obvykle používají k rozhodnutí, zda nějaký matematický objekt (například graf nebo booleovská funkce ) má „globální“ vlastnost, nebo je „daleko“ od toho, aby tuto vlastnost měl, pomocí pouze malého počtu „místních“ dotazů objekt.

Například následující problém slibu připouští algoritmus, jehož složitost dotazu je nezávislá na velikosti instance (pro libovolnou konstantu ε> 0):

"Vzhledem k grafu G na n vrcholech rozhodněte, zda G je bipartitní , nebo G nelze vytvořit bipartitní ani po odstranění libovolné podmnožiny na většině okrajů G. " ${\ displaystyle \ epsilon {\ tbinom {n} {2}}}$

Algoritmy testování vlastností jsou ústředním bodem definice pravděpodobnostně ověřitelných důkazů , protože pravděpodobnostně ověřitelný důkaz je v podstatě důkaz, který lze ověřit algoritmem testování vlastností.

Definice a varianty

Formálně, nemovitosti testování algoritmus se složitostí dotaz q ( n ) a proximity parametr epsilon rozhodnutí problému L je randomizované algoritmus , který na vstup x (instanci L ) činí nejvýše q (| x |) dotazy x a chová se takto:

• Pokud je x v L , algoritmus přijímá x s pravděpodobností alespoň ⅔.
• Pokud je x daleko od L , algoritmus odmítne x s pravděpodobností alespoň ⅔.

Zde „ x je ε-daleko od L “ znamená, že Hammingova vzdálenost mezi x a jakýmkoli řetězcem v L je alespoň ε | x |.

Algoritmus testování vlastností má jednostrannou chybu, pokud splňuje silnější podmínku, že pravděpodobnost přijetí pro instance x ∈ L je 1 místo ⅔.

Algoritmus testování vlastností je považován za neadaptivní, pokud provádí všechny své dotazy, než „pozoruje“ jakékoli odpovědi na předchozí dotazy. Na takový algoritmus lze pohlížet jako na fungující následujícím způsobem. Nejprve algoritmus přijme svůj vstup. Než se podíváme na vstup pomocí jeho vnitřní náhodnosti, algoritmus rozhodne, které symboly vstupu mají být dotazovány. Algoritmus dále tyto symboly sleduje. Nakonec algoritmus bez dalších dotazů (ale možná s využitím jeho náhodnosti) rozhodne, zda vstup přijme nebo odmítne.

Funkce a omezení

Hlavním parametrem účinnosti algoritmu testování vlastností je jeho složitost dotazu, což je maximální počet vstupních symbolů kontrolovaných přes všechny vstupy dané délky (a všechny náhodné volby provedené algoritmem). Jeden se zajímá o navrhování algoritmů, jejichž složitost dotazů je co nejmenší. V mnoha případech je doba běhu algoritmů testování vlastností sublearní v délce instance. Cílem je obvykle nejprve co nejmenší složitost dotazu v závislosti na velikosti instance n a poté studovat závislost na parametru blízkosti ε.

Na rozdíl od jiných teoreticko-složitých nastavení je složitost asymptotických dotazů algoritmů testování vlastností dramaticky ovlivněna reprezentací instancí. Například, když ε = 0,01, problém testování bipartitity hustých grafů (které jsou reprezentovány jejich maticí sousedství ) připouští algoritmus konstantní složitosti dotazu. Naproti tomu řídké grafy na n vrcholech (které jsou reprezentovány jejich seznamem sousedů) vyžadují algoritmy testování vlastností složitosti dotazu . ${\ displaystyle \ Omega ({\ sqrt {n}})}$

Složitost dotazů algoritmů testování vlastností roste s tím, jak se parametr blízkosti ε zmenšuje pro všechny netriviální vlastnosti. Tato závislost na ε je nezbytná, protože změnu méně než ε symbolů na vstupu nelze detekovat s konstantní pravděpodobností pomocí méně než O (1 / ε) dotazů. Mnoho zajímavých vlastností hustých grafů lze testovat pomocí složitosti dotazu, která závisí pouze na ε a ne na velikosti grafu n . Složitost dotazu však může enormně rychle růst jako funkce ε. Například, po dlouhou dobu nejlépe známý algoritmus pro testování v případě, že graf nebude obsahovat žádné trojúhelníku měla složitost dotazu, který je funkce věž z poly (1 / ε), a až v roce 2010 to bylo vylepšeno funkce věž z log (1 / epsilon). Jedním z důvodů tohoto enormního nárůstu mezí je to, že mnoho pozitivních výsledků pro testování vlastností grafů je stanoveno pomocí Szemerédiho pravidelného lematu , které má ve svých závěrech také meze věžového typu. Níže je rozpracováno propojení testování vlastností s lemem pravidelnosti Szemerédi a souvisejícími lemmy pro odstranění grafů.

Testování vlastností grafů

U grafů s n vrcholy je pojem vzdálenosti, který použijeme, vzdálenost pro úpravy. To znamená, že říkáme, že vzdálenost mezi dvěma grafy je nejmenší ε, takže lze přidávat a / nebo mazat hrany a dostat se z prvního grafu do druhého. Při rozumném znázornění grafů je to ekvivalentní dřívější definici Hammingovy vzdálenosti (až do případné změny konstant). U grafů existuje charakteristika vlastností, které lze snadno otestovat. Vlastnosti, které lze snadno otestovat, jsou přesně ty vlastnosti, které jsou (téměř) dědičné. Tato prohlášení budou objasněna níže. Za prvé, vlastností, kterou lze snadno otestovat, máme na mysli, že má zapomenutého testera. ${\ displaystyle \ varepsilon n ^ {2}}$

Nezapomenutelní testeři

Nezapomenutelný tester pro vlastnost grafu P je neformálně algoritmus, který bere jako vstup parametr ε a graf G , a poté běží jako algoritmus testování vlastnosti na G pro vlastnost P s parametrem blízkosti ε, který dává přesně q (ε) dotazy na G . Klíčové je, že počet dotazů, které zapomíná tester, je konstanta závislá pouze na ε. Formální definice je, že zapomnětlivý tester je algoritmus, který bere jako vstup parametr ε. Vypočítá celé číslo q (ε) a poté požádá věštce o indukovaný podgraf H na přesně q (ε) vrcholech z G vybraných náhodně jednotně. To pak přijme nebo odmítne podle £ a H . Stejně jako dříve, říkáme testuje pro vlastnost P, pokud se přijme s pravděpodobností nejméně ⅔ pro G , který má vlastnost P , a odmítá s pravděpodobností nejméně ⅔ nebo G , který je ε-daleko od mít vlastnost P . V úplné analogii s algoritmy testování vlastností můžeme hovořit o zapomnětlivých testerech s jednostrannou chybou.

Testování dědičných vlastností

Dědičná vlastnost je vlastnost, která je zachována v rámci vypuštění vrcholů. Několik důležitých dědičných vlastností je H -freeness (pro nějaký graf H ), k -barevnost a rovinnost . Všechny dědičné vlastnosti jsou testovatelné a o této skutečnosti existuje důkaz pomocí verze lemmatu pro odstranění grafu pro nekonečné rodiny indukovaných podgrafů. Ve skutečnosti je to také hrubý opak - vlastnosti, které mají zapomínající testery s jednostrannou chybou, jsou téměř dědičné (Alon & Shapira 2008), v tom smyslu, který zde nebude upřesněn.

Příklad: testování trojúhelníkové volnosti

V této části načrtneme důkaz o existenci zapomínajícího testeru na trojúhelníkovost; tento důkaz je aplikace lemu pro odstranění trojúhelníku .

Náčrt důkazu: Pokud je graf G daleko od toho, aby byl bez trojúhelníků, pak podle lemu pro odstranění trojúhelníku existuje (vypočítatelná) konstanta, takže G má alespoň trojúhelníky. Nezapomenutelný tester náhodně vzorkuje trojnásobek vrcholů náhodně z grafu. Přijme, pokud žádný trojnásobek vrcholů nevyvolá trojúhelník, a odmítne to jinak. ${\ displaystyle \ delta = \ delta (\ varepsilon)}$${\ displaystyle \ delta n ^ {3}}$${\ displaystyle q (\ varepsilon) = 1 / \ delta}$

• Pokud je G bez trojúhelníků, pak tento algoritmus jasně vždy přijímá.
• Pokud G není daleko od trojúhelníku, pak více než zlomek trojic vrcholů v G indukuje trojúhelník a pak není těžké vidět, že existuje větší než ⅔ šance, že algoritmus najde alespoň jeden trojúhelník. ${\ displaystyle 6 / \ delta}$

Proto je výše uvedený algoritmus zapomnětlivým testerem s jednostrannou chybou pro trojúhelníkovost.

Reference

• Goldreich, Oded (2017). Úvod do testování vlastností . Cambridge University Press. ISBN   9781107194052 .
• Ron, Dana (2000). Testování vlastností (technická zpráva).
• Rubinfeld, Ronitt; Shapira, Asaf (2011). "Sublearské časové algoritmy". SIAM Journal on Discrete Mathematics . 25 (4): 1562–1588. CiteSeerX   10.1.1.221.1797 . doi : 10.1137 / 100791075 .
• Goldreich, Oded (1999). "Kombinatorické testování vlastností (průzkum)" . Metody randomizace v návrhu algoritmu . 43 : 45–59. ISBN   0821870874 .
• Fox, Jacob (2010). Msgstr "Nový důkaz lemmatu pro odstranění grafu". arXiv : 1006,1300 .
• Alon, Noga ; Shapira, Asaf (2008). "Charakterizace (přirozených) vlastností grafu testovatelná jednostrannou chybou" (PDF) . SIAM Journal on Computing . 37 : 1703–1727.