Randomness and Nondeterminism

Leonid A. Levin
Additional contact information
Leonid A. Levin: Boston University, Computer Science Department

A chapter in Proceedings of the International Congress of Mathematicians, 1995, pp 1418-1419 from Springer

Abstract: Abstract Exponentiation makes the difference between the bit size of this line and the number (“ 2300) of particles in the known universe. The expulsion of exponential time algorithms from computer theory in the 1960s created a deep gap between deterministic computation and — formely its unremarkable tools — randomness and nondeterminism. These two “freedom” of computation preserved their reputation as some of the most mysterious phenomena in science and seem to play an ever more noticeable role in computer theory. We have learned little in the past decades about the power of either, but a vague pattern is emerging in their relationships.

Date: 1995
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-3-0348-9078-6_137

Ordering information: This item can be ordered from
http://www.springer.com/9783034890786

DOI: 10.1007/978-3-0348-9078-6_137

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().