Randomizing Reductions of Search Problems

DOI10.1137/0222059MaRDI QIDQ3142587zbMATH OpenOpenAlexFDO

Authors 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)

Recommendations

• scientific article; zbMATH DE number 1332675
• Structural average case complexity
• Reductions do not preserve fast convergence rates in average time
• Average case complexity, revisited
• scientific article; zbMATH DE number 8776

Cited in

(12)

• The complexity of generating test instances
• No NP problems averaging over ranking of distributions are harder
• scientific article; zbMATH DE number 3453517 (Why is no real title available?)
• scientific article; zbMATH DE number 3423964 (Why is no real title available?)
• The power of adaptiveness and additional queries in random-self- reductions
• On the complexity of deadlock detection in families of planar nets
• Complete on average Boolean satisfiability
• Importance of search-domain reduction in random optimization
• Rankable distributions do not provide harder instances than uniform distributions
• One side cut accelerated random search
• Polynomial time samplable distributions
• A Random NP-complete problem for inversion of 2D cellular automata

This page was built for publication: Randomizing Reductions of Search Problems

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