Test af ejendom - Property testing

I datalogi er en egenskabstestalgoritme for et beslutningsproblem en algoritme, hvis forespørgselskompleksitet til dens input er meget mindre end problemets forekomststørrelse . Typisk bruges egenskabstestalgoritmer til at afgøre, om et matematisk objekt (såsom en graf eller en boolsk funktion ) har en "global" egenskab eller er "langt" fra at have denne egenskab ved kun at bruge et lille antal "lokale" forespørgsler til genstanden.

For eksempel følgende løfte problemet indrømmer en algoritme, hvis forespørgsel kompleksitet er uafhængig af instans størrelse (for en arbitrær konstant ε> 0):

"Givet en graf G på n- hjørner, skal du beslutte, om G er bipartit , eller G ikke kan gøres bipartit, selv efter at have fjernet en vilkårlig delmængde af højst kanter af G. " ${\ displaystyle \ epsilon {\ tbinom {n} {2}}}$

Ejendomsafprøvningsalgoritmer er centrale for definitionen af sandsynligt kontrollerbare bevis , da et sandsynligt kontrollerbart bevis i det væsentlige er et bevis, der kan verificeres af en egenskabstestningsalgoritme.

Definition og varianter

Formelt er en egenskabstestealgoritme med forespørgselskompleksitet q ( n ) og nærhedsparameter ε for et beslutningsproblem L en randomiseret algoritme , der på input x (en forekomst af L ) højst stiller q (| x |) forespørgsler til x og opfører sig som følger:

• Hvis x er i L , accepterer algoritmen x med sandsynlighed mindst ⅔.
• Hvis x er ε-langt fra L , afviser algoritmen x med sandsynlighed mindst ⅔.

Her betyder " x er ε-langt fra L ", at Hamming-afstanden mellem x og en hvilken som helst streng i L er mindst ε | x |.

En egenskabstestealgoritme siges at have ensidig fejl, hvis den tilfredsstiller den stærkere betingelse, at den accepterende sandsynlighed for forekomster x ∈ L er 1 i stedet for ⅔.

En egenskabstestealgoritme siges at være ikke-adaptiv, hvis den udfører alle sine forespørgsler, før den "observerer" eventuelle svar på tidligere forespørgsler. En sådan algoritme kan ses som værende på følgende måde. Først modtager algoritmen sit input. Før vi kigger på indgangen ved hjælp af dens interne tilfældighed, bestemmer algoritmen, hvilke symboler på indgangen der skal forespørges. Derefter observerer algoritmen disse symboler. Endelig, uden at stille yderligere forespørgsler (men muligvis bruge dens tilfældighed), bestemmer algoritmen, om input skal accepteres eller afvises.

Funktioner og begrænsninger

Den vigtigste effektivitetsparameter for en egenskabstestealgoritme er dens forespørgselskompleksitet, hvilket er det maksimale antal indgangssymboler, der er inspiceret over alle input af en given længde (og alle tilfældige valg foretaget af algoritmen). Man er interesseret i at designe algoritmer, hvis forespørgselskompleksitet er så lille som muligt. I mange tilfælde er køretidens algoritmers sublinear i instanslængden . Typisk er målet først at gøre forespørgslens kompleksitet så lille som muligt som en funktion af instansstørrelsen n og derefter undersøge afhængigheden af ​​nærhedsparameteren ε.

I modsætning til andre kompleksitetsteoretiske indstillinger påvirkes den asymptotiske forespørgselskompleksitet af algoritmer for ejendomstest dramatisk af repræsentationen af ​​forekomster. For eksempel, når ε = 0,01, indrømmer problemet med at teste dobbeltartethed af tætte grafer (som er repræsenteret af deres nærhedsmatrix ) en algoritme med konstant forespørgselskompleksitet. I modsætning hertil kræver sparsomme grafer på n hjørner (som er repræsenteret af deres nærhedsliste) egenskabstestingsalgoritmer med forespørgselskompleksitet . ${\ displaystyle \ Omega ({\ sqrt {n}})}$

Forespørgselens kompleksitet af egenskabstestalgoritmer vokser, når nærhedsparameteren ε bliver mindre for alle ikke-trivielle egenskaber. Denne afhængighed af ε er nødvendig, da en ændring af færre end ε-symboler i input ikke kan detekteres med konstant sandsynlighed ved hjælp af færre end O (1 / ε) forespørgsler. Mange interessante egenskaber ved tætte grafer kan testes ved hjælp af forespørgselskompleksitet, der kun afhænger af ε og ikke af grafstørrelsen n . Forespørgselens kompleksitet kan dog vokse enormt hurtigt som en funktion af ε. For eksempel havde den mest kendte algoritme til testning i lang tid, hvis en graf ikke indeholder nogen trekant, en forespørgselskompleksitet, som er en tårnfunktion af poly (1 / ε), og kun i 2010 er dette blevet forbedret til en tårnfunktion af log (1 / ε). En af grundene til denne enorme vækst i grænserne er, at mange af de positive resultater for ejendomstest af grafer er etableret ved hjælp af Szemerédi-regelmæssighedslemmet , som også har tårnegrænser i sine konklusioner. Forbindelsen af ​​ejendomstestning til Szemerédi-regelmæssighedslemmaet og relaterede graffjerningslemmaer er nærmere beskrevet nedenfor.

Ejendomstest af grafer

For grafer med n hjørner er begrebet afstand, vi vil bruge, redigeringsafstanden. Det vil sige, at vi siger, at afstanden mellem to grafer er den mindste ε, således at man kan tilføje og / eller slette kanter og komme fra den første graf til den anden. Under en rimelig gengivelse af grafer svarer dette til den tidligere definition af Hamming-afstand (op til muligvis en ændring af konstanter). For grafer er der en karakterisering af hvilke egenskaber der er lette at teste. Egenskaberne, der er lette at teste, er netop de egenskaber, der er (næsten) arvelige. Disse udsagn vil blive tydeliggjort nedenfor. Først og fremmest ved at en ejendom er let at teste, mener vi, at den har en glemsom tester. ${\ displaystyle \ varepsilon n ^ {2}}$

Uvidende testere

Uformelt er en glemsom tester for en grafegenskab P en algoritme, der tager som input en parameter ε og graf G og derefter kører som en egenskabstestealgoritme på G for egenskaben P med nærhedsparameter ε, der foretager nøjagtige q (ε) forespørgsler til G . Det afgørende er, at antallet af forespørgsler, som en glemsom tester foretager, er konstant kun afhængig af ε. Den formelle definition er, at en glemsom tester er en algoritme, der tager som parameter en parameter ε. Det beregner et heltal q (ε) og beder derefter et orakel om en induceret undergraf H på nøjagtigt q (ε) hjørner fra G valgt tilfældigt tilfældigt. Derefter accepterer eller afviser ifølge ε og H . Som før, siger vi det tester for ejendommen P hvis den accepterer med sandsynlighed mindst ⅔ til G , der har ejendom P , og afviser med sandsynlighed mindst ⅔ eller G , der er ε-langt fra at have ejendom P . I komplet analogi med egenskabstestalgoritmer kan vi tale om glemsomme testere med ensidig fejl.

Test af arvelige egenskaber

En arvelig ejendom er en ejendom, der bevares under sletning af hjørner. Et par vigtige arvelige egenskaber er H -freeness (for nogle graf H ), k -colorability , og planhed . Alle arvelige egenskaber er testbare, og der er et bevis på dette ved hjælp af en version af graffjerningslemmet for uendelige familier af inducerede underbilleder. Faktisk er en grov omvendt af dette også sandt - egenskaberne, der har glemme testere med ensidig fejl, er næsten arvelige (Alon & Shapira 2008) i en forstand, der ikke vil blive præciseret her.

Eksempel: test af trekantfrihed

I dette afsnit tegner vi et bevis på eksistensen af ​​en glemsom tester for trekantfrihed; dette bevis er en anvendelse af trekanten fjernelse lemma .

Skitse af bevis: Hvis en graf G er ε-langt fra at være trekantfri, så er der ved lemmaet til fjernelse af trekanten en (beregningsbar) konstant, så G har mindst trekanter. Den glemme testprøve tredobler hjørner uafhængigt tilfældigt fra grafen. Det accepteres, hvis ingen tredobbelt hjørner inducerer en trekant og afviser andet. ${\ displaystyle \ delta = \ delta (\ varepsilon)}$${\ displaystyle \ delta n ^ {3}}$${\ displaystyle q (\ varepsilon) = 1 / \ delta}$

• Hvis G er trekantfrit, accepterer denne algoritme altid altid.
• Hvis G er ε-langt fra at være trekantfrit, inducerer en mere end brøkdel af tredoblerne af hjørner i G en trekant, og så er det ikke svært at se, at der er større end ⅔ chance for, at algoritmen finder mindst en trekant. ${\ displaystyle 6 / \ delta}$

Derfor er algoritmen ovenfor en glemsom tester med ensidig fejl for trekantfrihed.

Referencer

• Goldreich, Oded (2017). Introduktion til test af ejendom . Cambridge University Press. ISBN   9781107194052 .
• Ron, Dana (2000). Ejendomstest (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). "Test af kombinatorisk ejendom (en undersøgelse)" . Randomiseringsmetoder i algoritmedesign . 43 : 45-59. ISBN   0821870874 .
• Fox, Jacob (2010). "Et nyt bevis på lemmaet til fjernelse af grafen". arXiv : 1006.1300 .
• Alon, Noga ; Shapira, Asaf (2008). "En karakterisering af (naturlige) grafegenskaber, der kan testes med ensidig fejl" (PDF) . SIAM Journal on Computing . 37 : 1703–1727.