Randomizing Reductions of Search Problems
From MaRDI portal
Publication:3142587
DOI10.1137/0222059zbMath0789.68056MaRDI 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
68R05: Combinatorics in computer science
60C05: Combinatorial probability
68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)
Related Items
A Random NP-complete problem for inversion of 2D cellular automata, On the complexity of deadlock detection in families of planar nets, No NP problems averaging over ranking of distributions are harder, Polynomial time samplable distributions, Complete on average Boolean satisfiability