Almost every 2-SAT function is unate

DOI10.1007/S11856-007-0081-ZMaRDI QIDQ2480593zbMATH OpenOpenAlexFDO

Authors Yanyan Li

Publication date 1 April 2008

Published in Israel Journal of Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s11856-007-0081-z

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Analysis of algorithms and problem complexity (68Q25) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Recommendations

• The number of 2-SAT functions
• Random 2-SAT: Results and problems
• On the number of 2-SAT functions
• Random 2-SAT and unsatisfiability
• The number of k‐SAT functions

Cites work

• Asymptotic Enumeration of Partial Orders on a Finite Set
• On the structure of clique-free graphs
• The average number of linear extensions of a partial order
• The maximum number of edges in a minimal graph of diameter 2
• The number of 2-SAT functions
• The number of k‐SAT functions

Cited in

(9)

• The number of 2-SAT functions
• The number of 3-SAT functions
• 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 number of 2-SAT functions
• The number of k‐SAT functions
• Combinatorics. Abstracts from the workshop held January 1--7, 2023
• Combinatorics, probability and computing. Abstracts from the workshop held April 24--30, 2022
• Turán problems for mixed graphs
• On the counting version of the maximum 2-satisfiability problem

This page was built for publication: Almost every 2-SAT function is unate

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