Matrix Transformation Is Complete for the Average Case

DOI10.1137/S0097539792232070zbMath0828.68078MaRDI QIDQ4326850

Andreas Blass, Yuri Gurevich

Publication date: 8 January 1996

Published in: SIAM Journal on Computing (Search for Journal in Brave)

zbMATH Keywords

average case complexityunimodular matrices

Mathematics Subject Classification ID

Matrix equations and identities (15A24) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Matrices of integers (15B36)

Related Items (14)

All \(\operatorname{SL}_{2}\)-tilings come from infinite triangulations ⋮ No NP problems averaging over ranking of distributions are harder ⋮ Rankable distributions do not provide harder instances than uniform distributions ⋮ Reductions and convergence rates of average time ⋮ A Random NP-complete problem for inversion of 2D cellular automata ⋮ ASYMPTOTIC DENSITY AND COMPUTABLY ENUMERABLE SETS ⋮ On complete one-way functions ⋮ An Average Case NP-complete Graph Colouring Problem ⋮ Algebraic cryptography: new constructions and their security against provable break ⋮ Generalized Learning Problems and Applications to Non-commutative Cryptography ⋮ Average-Case Completeness in Tag Systems ⋮ On the complexity of deadlock detection in families of planar nets ⋮ Complete distributional problems, hard languages, and resource-bounded measure ⋮ Public-key cryptography and invariant theory

This page was built for publication: Matrix Transformation Is Complete for the Average Case