Revisiting a result of Ko

DOI10.1016/S0020-0190(97)00197-XMaRDI QIDQ286990zbMATH OpenFDO

Authors Patrizio Cintioli, Riccardo Silvestri

Publication date 26 May 2016

Published in Information Processing Letters (Search for Journal in Brave)

zbMATH Keywords

computational complexitytheory of computationrelativizationsrobust algorithms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• Helping by unambiguous computation and probabilistic computation
• On helping by parity-like languages
• \(\mathrm{UP}\) and the low and high hierarchies: a relativized separation
• Complexity classes without machines: on complete languages for UP
• Separability and one-way functions

Cites work

• scientific article; zbMATH DE number 3984573 (Why is no real title available?)
• scientific article; zbMATH DE number 512802 (Why is no real title available?)
• scientific article; zbMATH DE number 1142309 (Why is no real title available?)
• Fault-tolerance and complexity (extended abstract)
• Helping by unambiguous computation and probabilistic computation
• On helping by robust oracle machines
• Robust algorithms: a different approach to oracles
• Self-reducibility

Cited in

(2)

• A note on quadratic residuosity and UP
• The Helping Hierarchy

This page was built for publication: Revisiting a result of Ko

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