Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
My Menu
Marked Items 
Alerts
Order History
Saved Items
All
Favorites
    
Book Chapter Printable view
Monte-Carlo Polynomial versus Linear Time - The Truth-Table Case

Monte-Carlo Polynomial versus Linear Time - The Truth-Table Case

Book SeriesLecture Notes in Computer Science
PublisherSpringer Berlin / Heidelberg
ISSN0302-9743 (Print) 1611-3349 (Online)
VolumeVolume 2138/2001
BookFundamentals of Computation Theory
DOI10.1007/3-540-44669-9
Copyright2001
ISBN978-3-540-42487-1
DOI10.1007/3-540-44669-9_30
Pages311-322
Subject CollectionComputer Science
SpringerLink DateMonday, January 01, 2001
Add to marked items

Monte-Carlo Polynomial versus Linear Time - The Truth-Table Case

Robert Rettinger5 Contact Information and Rutger Verbeek5 Contact Information

(5)  Dep. of computer science, Theoretische Informatik II, FernUniversität Hagen, D-58084 Hagen, Germany
Abstract
We show that under some truth-table oracle B there are almost exponential gaps in the (infinite often) hierarchy of bounded-error probabilistic time, in particular BPP tt B = ZPTIME tt B (n). This proves a main theorem in [5], which is extended to the theoretical limit.

Contact Information Robert Rettinger
Email: Robert.Rettinger@fernuni-hagen.de

Contact Information Rutger Verbeek
Email: Rutger.Verbeek@fernuni-hagen.de
Fulltext Preview (Small, Large)
Image of the first page of the fulltext

References secured to subscribers.
more options
Find


Export this chapter
Export this chapter as RIS | Text
 
Frequently asked questions | General information on journals and books | Send us your feedback | Impressum | Contact
© Springer. Part of Springer Science+Business Media
Privacy, Disclaimer, Terms and Conditions, © Copyright Information
Remote Address: 38.107.191.108 • Server: mpweb03
HTTP User Agent: CCBot/1.0 (+http://www.commoncrawl.org/bot.html)