An Explicit Separation of Relativised Random Polynomial Time and Relativised Deterministic Polynomial Time
Abstract
This note demonstrates that a certain class of naturally occurring problems involving an oracle are solvable in random polynomial time, but not in deterministic polynomial time. This class of problems is especially interesting because a very slight change in the parameters of the problem yields one that does have a polynomial solution.
Document Details
- Document Type
- Technical Report
- Publication Date
- Feb 01, 1989
- Accession Number
- ADA210103
Entities
People
- Richard Zippel
Organizations
- Cornell University