Matrix Transformation Is Complete for the Average Case

DOI10.1137/S0097539792232070zbMATH Open0828.68078MaRDI QIDQ4326850FDOQ4326850

Authors: Andreas Blass, Yuri Gurevich 

Publication date: 8 January 1996

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

Recommendations

• scientific article; zbMATH DE number 1072538
• scientific article; zbMATH DE number 1008518
• On the Average Case Complexity of Some P-complete Problems
• scientific article; zbMATH DE number 1263208
• scientific article; zbMATH DE number 5081744

zbMATH Keywords

average case complexityunimodular matrices

Mathematics Subject Classification ID

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

Cited In (14)

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

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

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