Time Bounded Frequency Computations

Authors: Hinrichs M.; Wechsung G.

Source: Information and Computation, Volume 139, Number 2, December 1997 , pp. 234-257(24)

Buy & download fulltext article:

Price: $52.63 plus tax (Refund Policy)

Abstract:

(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) P for m<2d. 2. (m, m+d) P=(m+1, m+d+1) P for m>=c(d) where c(d) is large enough.This disproves a conjecture of Kinber. (2) We give a transparent proof of ageneralization of Kinber's result that there exist arbitrarilycomplex problems admitting a polynomial time frequency computation.Several corollaries provide more insight into the structureof the hierarchy of polynomial time frequency classes. (3) Therelationships between polynomial time frequency classes andselectivity classes are studied. Copyright 1997 AcademicPress

Language: English

Document Type: Research article

Affiliations: Institut fur Informatik, Friedrich-Schiller-Universitat Jena, Jena, 07743, Germany

Publication date: 1997-12-01