scientific article; zbMATH DE number 512799

MaRDI QIDQ4281492zbMATH OpenFDO

Authors Jay Belanger, Jie Wang

Publication date 2 June 1994

zbMATH Keywords

average-case complexity classesmany-one reductionsnondeterministic Turing machinespolynomial-time computable distributionsrandomized decision problems

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• On the theory of average case complexity
• Structural average case complexity
• scientific article; zbMATH DE number 5081744

Cited in

(15)

• On the theory of average case complexity
• Some properties of sets tractable under every polynomial-time computable distribution
• No NP problems averaging over ranking of distributions are harder
• The difference between polynomial-time many-one and truth-table reducibilities on distributional problems
• Structural average case complexity
• Average-case non-approximability of optimisation problems
• scientific article; zbMATH DE number 1688354 (Why is no real title available?)
• Average polynomial time is hard for exponential time under sn-reductions
• Complete problems with L-samplable distributions
• Fundamentals of Computation Theory
• On the polynomial IO-complexity
• Rankable distributions do not provide harder instances than uniform distributions
• Reductions and convergence rates of average time
• Structure in average case complexity
• Relations between average-case and worst-case complexity

This page was built for publication:

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