On sufficient conditions for unsatisfiability of random formulas

DOI10.1145/972639.972645MaRDI QIDQ5501191zbMATH OpenOpenAlexFDO

Authors Albert Atserias

Publication date 1 August 2015

Published in Journal of the ACM (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/972639.972645

Mathematics Subject Classification ID

Classical propositional logic (03B05) Logic in computer science (03B70) Complexity of proofs (03F20) Logic programming (68N17) Descriptive complexity and finite models (68Q19) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• scientific article; zbMATH DE number 1775444
• Recognizing more random unsatisfiable 3-SAT instances efficiently
• A sharp threshold in proof complexity
• Automata, Languages and Programming
• Short propositional refutations for dense random 3CNF formulas

Cited in

(12)

• Space proof complexity for random 3-CNFs
• On digraph coloring problems and treewidth duality
• A combinatorial characterization of resolution width
• A framework for space complexity in algebraic proof systems
• scientific article; zbMATH DE number 5845490 (Why is no real title available?)
• A finite-model-theoretic view on propositional proof complexity
• Random unary predicates: Almost sure theories and countable models
• Definable Inapproximability: New Challenges for Duplicator
• A sharp threshold in proof complexity
• Constructing hard examples for graph isomorphism
• Lower bounds for DNF-refutations of a relativized weak pigeonhole principle
• QBF merge resolution is powerful but unnatural

This page was built for publication: On sufficient conditions for unsatisfiability of random formulas

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