UNIFORM CHARACTERIZATIONS OF COMPLEXITY CLASSES OF FUNCTIONS

Article Properties
  • Language
    English
  • DOI (url)
    10.1142/s0129054100000326
  • Publication Date
    2000/12/01
  • Journal
    International Journal of Foundations of Computer Science
  • Indian UGC (Journal)
  • Refrences
    23
  • SVEN KOSUB Theoretische Informatik, Julius-Maximilians-Universität Würzburg, Am Hubland, D-97074 Würzburg, Germany
  • HEINZ SCHMITZ Theoretische Informatik, Julius-Maximilians-Universität Würzburg, Am Hubland, D-97074 Würzburg, Germany
  • HERIBERT VOLLMER Theoretische Informatik, Julius-Maximilians-Universität Würzburg, Am Hubland, D-97074 Würzburg, Germany
Abstract
Login
Cite
KOSUB, SVEN, et al. “UNIFORM CHARACTERIZATIONS OF COMPLEXITY CLASSES OF FUNCTIONS”. International Journal of Foundations of Computer Science, vol. 11, no. 04, 2000, pp. 525-51, https://doi.org/10.1142/s0129054100000326.
KOSUB, S., SCHMITZ, H., & VOLLMER, H. (2000). UNIFORM CHARACTERIZATIONS OF COMPLEXITY CLASSES OF FUNCTIONS. International Journal of Foundations of Computer Science, 11(04), 525-551. https://doi.org/10.1142/s0129054100000326
KOSUB S, SCHMITZ H, VOLLMER H. UNIFORM CHARACTERIZATIONS OF COMPLEXITY CLASSES OF FUNCTIONS. International Journal of Foundations of Computer Science. 2000;11(04):525-51.
Journal Categories
Science
Mathematics
Instruments and machines
Electronic computers
Computer science
Science
Mathematics
Instruments and machines
Electronic computers
Computer science
Computer software
Technology
Electrical engineering
Electronics
Nuclear engineering
Electronics
Computer engineering
Computer hardware
Description

This paper introduces a general framework for defining function classes based on nondeterministic polynomial-time Turing transducers. The model allows uniform characterizations of various complexity classes, including FP, FP NP, counting classes (#·P, #·NP), optimization classes (max·P, min·P), and promise classes. Each class is defined by how to evaluate computation trees of nondeterministic machines. A reducibility notion between evaluation schemes leads to a criterion for relativizable inclusion between function classes. This criterion is easily applicable, resulting in the conclusion that there is an oracle A such that min · P A⊈#· NP A. This result provides a separation that no structural consequences are known to follow from the corresponding positive inclusion.

Published in the International Journal of Foundations of Computer Science, this paper falls directly within the journal's scope by presenting new characterizations and relationships between computational complexity classes. The work advances the theoretical understanding of computation and the limits of efficient computation, which are central themes in the foundations of computer science.

Refrences
Login