Randomizing Reductions of Search Problems
From MaRDI portal
Publication:3142587
DOI10.1137/0222059zbMath0789.68056OpenAlexW2019084979MaRDI QIDQ3142587
Publication date: 20 December 1993
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0222059
Combinatorics in computer science (68R05) Combinatorial probability (60C05) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items (7)
Complete on average Boolean satisfiability ⋮ The complexity of generating test instances ⋮ No NP problems averaging over ranking of distributions are harder ⋮ Rankable distributions do not provide harder instances than uniform distributions ⋮ A Random NP-complete problem for inversion of 2D cellular automata ⋮ On the complexity of deadlock detection in families of planar nets ⋮ Polynomial time samplable distributions
This page was built for publication: Randomizing Reductions of Search Problems