The equivalence of Horn and network complexity for Boolean functions

DOI10.1007/BF00289267zbMath0477.94034OpenAlexW2042029993MaRDI QIDQ1160604

Egon Börger, Stal O. Anderaa

Publication date: 1981

Published in: Acta Informatica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf00289267

zbMATH Keywords

Horn formulacomplexity measure for logical functionsHorn complexityquasi-Horn formula

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Classical propositional logic (03B05)

Related Items (3)

Learning Boolean specifications ⋮ Transformations into Normal Forms for Quantified Circuits ⋮ Resolution and Expressiveness of Subclasses of Quantified Boolean Formulas and Circuits

Cites Work

• Komplexität von Entscheidungsproblemen. Ein Seminar
• The network complexity and the Turing machine complexity of finite functions
• Complete problems for deterministic polynomial time
• Beitrag zur Reduktion des Entscheidungsproblems auf Klassen von Hornformeln mit kurzen Alternationen
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: The equivalence of Horn and network complexity for Boolean functions