Explicit Separation of Relativised Random Polynomial Time and Relativesed Deterministic Polynomial Time

摘要

This note demonstrates that a certain class of naturally occuring 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. (jhd)