Time Bounded Frequency Computations

Authors: Hinrichs M.; Wechsung G.

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

Publisher: Academic Press

Key:

- Free Content

- New Content

- Subscribed Content

- Free Trial Content

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:

The full text electronic article is available for purchase. You will be able to download the full text electronic article after payment.

$54.38 plus tax Refund Policy