On sufficient conditions for unsatisfiability of random formulas

DOI10.1145/972639.972645zbMATH Open1316.68055OpenAlexW2123581574MaRDI QIDQ5501191FDOQ5501191

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

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

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)

Cited In (12)

• Title not available (Why is that?)
• 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)