Eiendomstesting - Property testing

I informatikk er en egenskapstestealgoritme for et avgjørelsesproblem en algoritme hvis spørringskompleksiteten til inngangen er mye mindre enn forekomsten av problemet. Vanligvis brukes algoritmer for testing av egenskaper for å bestemme om noe matematisk objekt (for eksempel en graf eller en boolsk funksjon ) har en "global" egenskap, eller er "langt" fra å ha denne egenskapen, og bruker bare et lite antall "lokale" spørsmål til objektet.

For eksempel, følgende løfte problem medgir en algoritme som spørring kompleksitet er uavhengig av forekomsten størrelse (for et vilkårlig konstant ε> 0):

"Gitt en graf G på n hjørner, bestem deg om G er tosidig , eller G kan ikke gjøres tosidig selv etter at du har fjernet en vilkårlig delmengde på de fleste kanter av G. " ${\ displaystyle \ epsilon {\ tbinom {n} {2}}}$

Eiendomstestealgoritmer er sentrale i definisjonen av sannsynlig kontrollerbare bevis , da et sannsynlig kontrollerbart bevis egentlig er et bevis som kan verifiseres av en algoritme for egenskapstesting.

Definisjon og varianter

Formelt er en egenskapstestealgoritme med spørringskompleksitet q ( n ) og nærhetsparameter ε for et beslutningsproblem L en randomisert algoritme som på inngang x (en forekomst av L ) maksimalt gjør q (| x |) spørsmål til x og oppfører seg slik:

• Hvis x er i L , aksepterer algoritmen x med sannsynlighet minst ⅔.
• Hvis x er ε-langt fra L , avviser algoritmen x med sannsynlighet minst ⅔.

Her betyr " x er ε-langt fra L " at Hamming-avstanden mellom x og en hvilken som helst streng i L er minst ε | x |.

En egenskapstestealgoritme sies å ha ensidig feil hvis den tilfredsstiller den sterkere forutsetningen at den akseptable sannsynligheten for forekomster x ∈ L er 1 i stedet for ⅔.

En egenskapstestealgoritme sies å være ikke-adaptiv hvis den utfører alle sine spørsmål før den "observerer" noen svar på tidligere spørsmål. En slik algoritme kan sees på som den fungerer på følgende måte. Først får algoritmen innspill. Før du ser på inngangen, ved hjelp av dens interne tilfeldighet, bestemmer algoritmen hvilke symboler på inngangen som skal spørres. Deretter observerer algoritmen disse symbolene. Til slutt, uten å gjøre noen ytterligere spørsmål (men muligens bruke tilfeldigheten), bestemmer algoritmen om den skal godta eller avvise inngangen.

Funksjoner og begrensninger

Hovedeffektivitetsparameteren til en egenskapstestealgoritme er spørringskompleksiteten, som er det maksimale antall inngangssymboler som er inspisert over alle innganger av en gitt lengde (og alle tilfeldige valg som gjøres av algoritmen). Man er interessert i å utforme algoritmer som har en så liten kompleksitet som mulig. I mange tilfeller er kjøretiden til algoritmer for eiendomstesting sublinear i forekomstens lengde. Vanligvis er målet først å gjøre spørringskompleksiteten så liten som mulig som en funksjon av forekomststørrelsen n , og deretter studere avhengigheten av nærhetsparameteren ε.

I motsetning til andre kompleksitetsteoretiske innstillinger, påvirkes den asymptotiske spørringskompleksiteten til egenskapstestealgoritmer dramatisk av representasjonen av forekomster. For eksempel, når ε = 0,01, innrømmer problemet med å teste toparter av tette grafer (som er representert ved deres nærhetsmatrise ) en algoritme med konstant spørringskompleksitet. I motsetning til dette, krever sparsomme grafer på n hjørner (som er representert ved deres nærhetsliste) egenskapstestingsalgoritmer av spørringskompleksitet . ${\ displaystyle \ Omega ({\ sqrt {n}})}$

Spørringskompleksiteten til algoritmer for eiendomstesting vokser når nærhetsparameteren ε blir mindre for alle ikke-trivielle egenskaper. Denne avhengigheten av ε er nødvendig da en endring på færre enn ε-symboler i inngangen ikke kan oppdages med konstant sannsynlighet ved å bruke færre enn O (1 / ε) spørsmål. Mange interessante egenskaper ved tette grafer kan testes ved hjelp av spørringskompleksitet som bare avhenger av ε og ikke av grafstørrelsen n . Spørringskompleksiteten kan imidlertid vokse enormt raskt som en funksjon av ε. For eksempel, i lang tid hadde den mest kjente algoritmen for testing om en graf ikke inneholder noen trekant, en forespørselskompleksitet som er en tårnfunksjon av poly (1 / ε), og bare i 2010 er dette blitt forbedret til en tårnfunksjon av logg (1 / ε). En av årsakene til denne enorme veksten i grensene er at mange av de positive resultatene for eiendomstesting av grafer er etablert ved hjelp av Szemerédi-regelmessighetslemmaet , som også har tårnegrenser i sine konklusjoner. Tilknytningen av eiendomstesting til Szemerédi-regelmessighetslemmaet og relaterte graffjerningslemma er utdypet nedenfor.

Eiendomstesting av grafer

For grafer med n hjørner er begrepet avstand vi vil bruke redigeringsavstanden. Det vil si at vi sier at avstanden mellom to grafer er den minste ε slik at man kan legge til og / eller slette kanter og komme fra den første grafen til den andre. Under en rimelig fremstilling av grafer tilsvarer dette den tidligere definisjonen av Hamming-avstand (opp til muligens en endring av konstanter). For grafer er det en karakterisering av hvilke egenskaper som er enkle å teste. Egenskapene som er enkle å teste er nettopp de egenskapene som er (nesten) arvelige. Disse uttalelsene vil bli gjort tydeligere nedenfor. Først av alt, ved at en eiendom er enkel å teste, mener vi at den har en glemsom tester. ${\ displaystyle \ varepsilon n ^ {2}}$

Glemmende testere

Uformelt er en glemsom tester for en grafegenskap P en algoritme som tar som inngang en parameter ε og graf G , og kjører deretter som en egenskapstestealgoritme på G for egenskapen P med nærhetsparameter ε som gjør nøyaktig q (ε) spørsmål til G . Avgjørende er at antall spørsmål en glemsom tester gjør er konstant bare avhengig av ε. Den formelle definisjonen er at en glemsom tester er en algoritme som tar som inndata en parameter ε. Den beregner et helt tall q (ε) og ber deretter et orakel om et indusert subgraf H på nøyaktig q (ε) hjørner fra G valgt jevnt tilfeldig. Den godtar deretter eller vrak i henhold til ε og H . Som før, sier vi det tester for egenskapen P hvis det tar med sannsynlighet minst ⅔ for G som har egenskapen P , og vrak med sannsynlighet minst ⅔ eller G som er ε-langt fra å ha egenskapen P . I fullstendig analogi med egenskapstestealgoritmer, kan vi snakke om glemmelige testere med ensidig feil.

Testing av arvelige egenskaper

En arvelig eiendom er en eiendom som er bevart under sletting av hjørner. Noen viktige arvelige egenskaper er H- frihet (for noen graf H ), k- fargelighet og planaritet . Alle arvelige egenskaper kan testes, og det er bevis på dette ved å bruke en versjon av graffjerningslemmaet for uendelige familier av induserte subgrafier. Faktisk er en grov omvendelse av dette også sant - egenskapene som har glemmende testere med ensidig feil er nesten arvelige (Alon & Shapira 2008), i en forstand som ikke vil bli presist her.

Eksempel: testing av trekantfrihet

I denne delen skal vi tegne et bevis på eksistensen av en glemsom tester for trekantfrihet; dette beviset er en anvendelse av trekanten fjerning lemma .

Bevisskisse: Hvis en graf G er ε-langt fra å være trekantfri, så er det ved hjelp av trekantfjerningslemmaet en (beregningsbar) konstant slik at G har minst trekanter. Den uvitende testeren prøver tredoblinger av hjørner uavhengig tilfeldig fra grafen. Det aksepteres hvis ingen trippel av hjørner induserer en trekant, og avviser noe annet. ${\ displaystyle \ delta = \ delta (\ varepsilon)}$${\ displaystyle \ delta n ^ {3}}$${\ displaystyle q (\ varepsilon) = 1 / \ delta}$

• Hvis G er trekantfritt, aksepterer denne algoritmen tydeligvis alltid.
• Hvis G er ε-langt fra å være trekantfritt, så induserer en mer enn brøkdel av tredoblene av hjørner i G en trekant, og da er det ikke vanskelig å se at det er større enn ⅔ sjansen for at algoritmen finner minst en triangel. ${\ displaystyle 6 / \ delta}$

Derfor er algoritmen ovenfor en uvitende tester med ensidig feil for trekantfrihet.

Referanser

• Goldreich, Oded (2017). Introduksjon til eiendomstesting . Cambridge University Press. ISBN   9781107194052 .
• Ron, Dana (2000). Eiendomstesting (teknisk rapport).
• Rubinfeld, Ronitt; Shapira, Asaf (2011). "Sublinear Time Algorithms". SIAM Journal on Discrete Mathematics . 25 (4): 1562–1588. CiteSeerX   10.1.1.221.1797 . doi : 10.1137 / 100791075 .
• Goldreich, Oded (1999). "Testing av kombinasjonsegenskap (en undersøkelse)" . Randomiseringsmetoder i algoritmedesign . 43 : 45–59. ISBN   0821870874 .
• Fox, Jacob (2010). "Et nytt bevis på lemma for fjerning av graf". arXiv : 1006.1300 .
• Alon, Noga ; Shapira, Asaf (2008). "En karakterisering av (naturlige) grafegenskaper som kan testes med ensidig feil" (PDF) . SIAM Journal on Computing . 37 : 1703–1727.