Randomness and completeness in computational complexity

MaRDI QIDQ1591868zbMATH OpenFDO

Authors Dieter Van Melkebeek

Publication date 10 January 2001

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

zbMATH Keywords

computational complexitycomplexity classesderandomizationpseudorandomnessrandom setsresource-bounded measurebounded reducibilitieshardness versus randomness trade-offsresource-bounded betting gamesresource-bounded betting strategies

Mathematics Subject Classification ID

Research exposition (monographs, survey articles) pertaining to computer science (68-02) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• A Generalization of Resource-Bounded Measure, with Application to the BPP vs. EXP Problem
• Probabilistic autoreductions
• Hard sets are hard to find
• Separating Complexity Classes Using Autoreducibility
• scientific article; zbMATH DE number 1335891

Cited in

(4)

• On randomized versus deterministic computation
• TuringMobile: a Turing machine of oblivious mobile robots with limited visibility and its applications
• Randomness – A Computational Complexity Perspective
• A Generalization of Resource-Bounded Measure, with Application to the BPP vs. EXP Problem

This page was built for publication: Randomness and completeness in computational complexity

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