Inverting a permutation is as hard as unordered search

DOI10.4086/toc.2011.v007a002zbMath1213.68287arXiv1007.2899OpenAlexW2168814002MaRDI QIDQ3002827

Ashwin Nayak

Publication date: 24 May 2011

Published in: Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1007.2899

zbMATH Keywords

quantum algorithmquery complexityrandomized reductionhybrid argumentinverting permutationsunordered search

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Quantum algorithms and complexity in the theory of computing (68Q12)

This page was built for publication: Inverting a permutation is as hard as unordered search