I&C Journal 1997 Journal Article
Time Bounded Frequency Computations
- Maren Hinrichs
- Gerd Wechsung
(1) We obtain two new results concerning the inclusion problem of polynomial time frequency classes with equal numbers of errors. 1. (m, m+d) P⊉(m+1, m+d+1) Pform<2 d. 2. (m, m+d) P=(m+1, m+d+1) Pform⩾c(d) wherec(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 into the structure of the hierarchy of polynomial time frequency classes. (3) The relationships between polynomial time frequency classes and selectivity classes are studied.