Random polynomial time is equal to slightly-random polynomial time
- 1 January 1985
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 417-428
- https://doi.org/10.1109/sfcs.1985.45
Abstract
Random Polynomial Time (Rp) is currently considered to be the class of tractable computational problems. Here one assumes a source of truly random bits. However, the known sources of randomness are imperfect. They can be modeled as an adversary source, called slightly-random source. Slightlyrandom Polynomial Time (SRp) is the class of problems solvable in polynomial time using such a source. SRp is thus a more realistic definition of a tractable computational problem. In this paper we give an affirmative answer to the question "is Rp = SRp?" Our proof method is constructive: given an Rp algorithm for a problem, we show how to obtain an SRp algorithm for it. Studying the relationship between randomized and deterministic computation is currently an important issue. A central question here is "is Rp = P?" Our result may be a step towards answering this question.Keywords
This publication has 15 references indexed in Scilit:
- Generating Quasi-Random Sequences From Slightly-Random SourcesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2005
- Independent Unbiased Coin Flips From A Correlated Biased Source: A Finite State Markov ChainPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2005
- Towards a strong communication complexity theory or generating quasi-random sequences from two communicating slightly-random sourcesPublished by Association for Computing Machinery (ACM) ,1985
- A simple parallel algorithm for the maximal independent set problemPublished by Association for Computing Machinery (ACM) ,1985
- NP is as easy as detecting unique solutionsPublished by Association for Computing Machinery (ACM) ,1985
- A complexity theoretic approach to randomnessPublished by Association for Computing Machinery (ACM) ,1983
- The complexity of approximate countingPublished by Association for Computing Machinery (ACM) ,1983
- Probabilistic algorithm for testing primalityJournal of Number Theory, 1980
- A Fast Monte-Carlo Test for PrimalitySIAM Journal on Computing, 1977
- Riemann's hypothesis and tests for primalityJournal of Computer and System Sciences, 1976