Testing Read-Once Formula Satisfaction

DOI10.1145/2897184MaRDI QIDQ4973849zbMATH OpenOpenAlexFDO

Authors Eldar Fischer, Yonatan Goldhirsh, Oded Lachish

Publication date 6 December 2019

Published in ACM Transactions on Computation Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1204.3413, https://eprints.bbk.ac.uk/id/eprint/14832/1/TFB.pdf

zbMATH Keywords

property testingread-once formulamassively parametrized properties

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Randomized algorithms (68W20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Abstract: We study the query complexity of testing for properties defined by read once formulas, as instances of {em massively parametrized properties}, and prove several testability and non-testability results. First we prove the testability of any property accepted by a Boolean read-once formula involving any bounded arity gates, with a number of queries exponential in $epsilon$, doubly exponential in the arity, and independent of all other parameters. When the gates are limited to being monotone, we prove that there is an {em estimation} algorithm, that outputs an approximation of the distance of the input from satisfying the property. For formulas only involving And/Or gates, we provide a more efficient test whose query complexity is only quasipolynomial in $epsilon$. On the other hand, we show that such testability results do not hold in general for formulas over non-Boolean alphabets; specifically we construct a property defined by a read-once arity $2$ (non-Boolean) formula over an alphabet of size $4$, such that any $1/4$-test for it requires a number of queries depending on the formula size. We also present such a formula over an alphabet of size $5$ that additionally satisfies a strong monotonicity condition.

Recommendations

• Testing formula satisfaction
• On reconstruction and testing of read-once formulas
• Testing read-once functions over the elementary basis
• Testing Monotone Read-Once Functions
• Testing a specification form in single functional index model
• scientific article; zbMATH DE number 2119722
• Amplification by Read-Once Formulas
• Testing Basic Boolean Formulae
• On the relationship between diagnostic and checking tests of the read-once functions
• Characterizing arithmetic read-once formulae

Cited in

(2)

• Some 3CNF Properties Are Hard to Test
• Testing formula satisfaction

This page was built for publication: Testing Read-Once Formula Satisfaction

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4973849)