Recognizing read-once functions from depth-three formulas
From MaRDI portal
Publication:5915579
DOI10.1007/978-3-319-90530-3_20zbMath1434.68200arXiv1802.03815MaRDI QIDQ5915579
Publication date: 28 November 2018
Published in: Theory of Computing Systems, Computer Science – Theory and Applications (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1802.03815
NP-completeness; monotone Boolean functions; coNP-completeness; read-once functions; depth-three formulas
68Q25: Analysis of algorithms and problem complexity
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
06E30: Boolean functions