Randomizing Reductions of Search Problems

DOI10.1137/0222059zbMath0789.68056OpenAlexW2019084979MaRDI QIDQ3142587

Andreas Blass, Yuri Gurevich

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

zbMATH Keywords

randomizationreductionaverage-case complexitysearch problem

Mathematics Subject Classification ID

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