On the weights of Boolean functions representable by 2-CNF or 3-CNF

DOI10.4213/MVK242MaRDI QIDQ3382008zbMATH OpenOpenAlexFDO

Authors S. P. Gorshkov, Alexey V. Tarasov

Publication date 20 September 2021

Published in Matematicheskie Voprosy Kriptografii [Mathematical Aspects of Cryptography] (Search for Journal in Brave)

Full work available at URL http://mathnet.ru/eng/mvk242

zbMATH Keywords

weight of Boolean function\(k\)-CNFbijunctive Boolean functions

Mathematics Subject Classification ID

Boolean functions (94D10)

Recommendations

• О методах оценивания веса булевых биюнктивных функций
• Bijunctive Boolean functions, graphs of 2-CNF and their order functions. Estimates of weight of a bijunctive function with a given number of layers
• On properties of functions representable in the form of a 2-CNF
• On the Boolean functions without upper bijunctive analogues
• Boolean functions with a simple certificate for CNF complexity

Cites work

• scientific article; zbMATH DE number 4039349 (Why is no real title available?)
• Solving satisfiability in less than \(2^ n\) steps
• The complexity of satisfiability problems

Cited in

(7)

• On properties of functions representable in the form of a 2-CNF
• Exclusive and essential sets of implicates of Boolean functions
• Boolean functions with a simple certificate for CNF complexity
• О методах оценивания веса булевых биюнктивных функций
• Any 2-asummable bipartite function is weighted threshold
• On the Boolean functions without upper bijunctive analogues
• Bijunctive Boolean functions, graphs of 2-CNF and their order functions. Estimates of weight of a bijunctive function with a given number of layers

This page was built for publication: On the weights of Boolean functions representable by 2-CNF or 3-CNF

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