On unique satisfiability and the threshold behavior of randomized reductions

DOI10.1006/jcss.1995.1028zbMath0837.68026OpenAlexW2052309234MaRDI QIDQ1894445

Jim Kadin, Richard Chang, 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

zbMATH Keywords

complexitysatisfiability

Mathematics Subject Classification ID

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

Related Items (8)

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

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