TIME BOUNDED FREQUENCY COMPUTATIONS

(1) We obtain two new results concerning the inclusion problem of poly nomial time frequency classes with equal numbers of errors. 1. (m, m d) P not superset of or equal to (m + 1, m + d + 1) P for m < 2(d).2. (m, m + d) P = (m + 1, m + d + 1) P for m greater than or equal to c( d) where c(d) is large enough. This disproves a conjecture of Kinber. (2) We give a transparent proof of a generalization of Kinber's result that there exist arbitrarily complex problems admitting a polynomial time frequency computation. Several corollaries provide more insight i nto the structure of the hierarchy of polynomial time frequency classe s. (3) The relationships between polynomial time frequency classes and selectivity classes are studied. (C) 1997 Academic Press.