Decision trees and downward closures
Russell Impagliazzo, Moni Naor · 1988
The separation of small complexity classes is considered. Some downward closure results are derived which show that some intuitively arrive at results that were published previously are misleading. This is done by giving uniform versions of simulations in the decision-tree model of concrete complexity. The results also show that sublinear-time computation has enough power to code interesting questions in polynomial-time complexity.>