Låt (I) vara en uppsättning allmänna booleska funktioner på n variabler, så att varje funktion beror på exakt k variabler, och varje variabel kan ta ett värde från [1,d]. Vi säger att ¢ är e-långt från satisfiable, om man måste ta bort minst en k funktioner för att göra uppsättningen av återstående funktioner satisfiable. Vårt huvudresultat är att om 4) är e- långt från satisfiable, då de flesta inducerade uppsättningar av funktioner, på uppsättningar av variabler av storlek c (k,d)/e 2, är inte tillfredsställande, där c (k, d) beror endast på k och d. Med hjälp av ovanstående påstående, vi få liknande resultat för k-SAT och k-NAEQ-SAT. Anta att vi löser beslutsproblemet om huruvida ett fall av ett av de ovan nämnda problemen är tillfredsställande eller inte, problemet med att avgöra om ett fall är tillfredsställande eller inte är tillfredsställande. Medan ovanstående beslutsproblem är NP-hårda, vårt resultat innebär att vi kan lösa deras avslappnade versioner, det vill säga skilja mellan tillfredsställande och e-långt från tillfredsställande fall, i randomiserad konstant tid. Av ovanstående resultat får vi som specialfall, tidigare resultat av Alon och Krivelevich [3] och av Czumaj och Sohler [8], om testning av grafer och hypergrafer färgbarhet. Vi diskuterar också problemet med att testa om en graf G kan färgas, så att den inte innehåller någon kopia av en färgad graf från en fast, given uppsättning färgade grafer.
Huvudresultatet av REF visar att eventuella problem med begränsningstillfredsställelse kan prövas.
Testing satisfiability
{'venue': "SODA '02", 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}