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

DOI10.4213/MVK242zbMATH Open1481.94167OpenAlexW2857459284MaRDI QIDQ3382008FDOQ3382008

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

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

zbMATH Keywords

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

Mathematics Subject Classification ID

Boolean functions (94D10)

Cites Work

• The complexity of satisfiability problems
• Solving satisfiability in less than \(2^ n\) steps
• Title not available (Why is that?)

Cited In (7)

• Boolean functions with a simple certificate for CNF complexity
• Exclusive and essential sets of implicates of Boolean functions
• On properties of functions representable in the form of a 2-CNF
• 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 the Boolean functions without upper bijunctive analogues
• О методах оценивания веса булевых биюнктивных функций
• Any 2-asummable bipartite function is weighted threshold

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)