An explicit separation of relativised random polynomial time and relativised deterministic polynomial time (Q918200)

An important problem in structural complexity theory is determining the relationship between the class of problems solvable in deterministic polynomial time and those solvable in random polynomial time. The author considers the problem of interpolating a sparse polynomial P from its values. An essential component of determining P is the somewhat simpler problem of showing that P is not the zero polynomial. It is shown that, given certain information about P, no deterministic polynomial time algorithm can distinguish P from the zero polynomial. It is shown, however, that there exist probabilistic algorithms that distinguish P from zero in random polynomial time. For the more general problem this implies that P cannot be determined in deterministic polynomial time and that yet there exist probabilistic polynomial algorithms.