Time Bounded Frequency Computations

(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.

Authors

• Maren Hinrichs
• Gerd Wechsung

Keywords

No keywords are indexed for this paper.