On unique satisfiability and the threshold behavior of randomized reductions

DOI10.1006/JCSS.1995.1028zbMATH Open0837.68026OpenAlexW2052309234MaRDI QIDQ1894445FDOQ1894445

Authors: Richard Chang, Jim Kadin, Pankaj Rohatgi 

Publication date: 21 August 1995

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/39e4cac5a50bfe520df8596adcfe59c59103a272

Recommendations

• scientific article; zbMATH DE number 8776
• The satisfiability threshold for a seemingly intractable random constraint satisfaction problem
• Approximating the unsatisfiability threshold of random formulas (extended abstract)
• scientific article; zbMATH DE number 7561554
• Approximating the unsatisfiability threshold of random formulas
• Approximating the Satisfiability Threshold for Random k-XOR-formulas
• Theory and Applications of Satisfiability Testing
• scientific article; zbMATH DE number 1775444
• The satisfiability threshold for randomly generated binary constraint satisfaction problems
• The satisfiability threshold for randomly generated binary constraint satisfaction problems

zbMATH Keywords

complexitysatisfiability

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Theory of software (68N99)

Cited In (9)

• On Existentially First-Order Definable Languages and Their Relation to NP
• The computational complexity of ideal semantics
• Saving queries with randomness
• On computing Boolean connectives of characteristic functions
• The landscape of communication complexity classes
• On the power of generalized Mod-classes
• The three-color and two-color Tantrix\(^{\text{TM}}\) rotation puzzle problems are NP-complete via parsimonious reductions
• Parameterized random complexity
• Monotonous and randomized reductions to sparse sets

This page was built for publication: On unique satisfiability and the threshold behavior of randomized reductions

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