Vi karakteriserar uppsättningen av egenskaper hos Booleska-värderade funktioner på en ändlig domän X som kan testas med ett konstant antal prover. Specifikt visar vi att en egenskap P är testbar med ett konstant antal prover om och endast om det är (i huvudsak) en k-del symmetrisk egenskap för vissa konstant k, där en egenskap är k-part symmetrisk om det finns en partition S 1,. .., S k X sådan att huruvida f : X → {0, 1} uppfyller fastigheten bestäms enbart av densiteterna f på S 1,. .., S k. Vi använder denna karakterisering för att få ett antal korollärer, nämligen: • En graf egenskap P kan testas med ett konstant antal prover om och endast om en graf G uppfyller P (i huvudsak) bestäms av kanten densitet G.
Ett nyligen utfört arbete av Blais och Yoshida REF kännetecknar egenskaperna P som har en konstant frågeprov-baserat test.
A Characterization of Constant-Sample Testable Properties
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}