scientific article; zbMATH DE number 512799

zbMath0788.68052MaRDI QIDQ4281492

Jay Belanger, Jie Wang

Publication date: 2 June 1994

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

nondeterministic Turing machinesmany-one reductionspolynomial-time computable distributionsaverage-case complexity classesrandomized decision problems

Mathematics Subject Classification ID

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

Related Items (3)

Some properties of sets tractable under every polynomial-time computable distribution ⋮ Rankable distributions do not provide harder instances than uniform distributions ⋮ Reductions and convergence rates of average time

This page was built for publication: