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

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

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)

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

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)