Turing machines with few accepting computations and low sets for PP
type: Item
instance of: scholarly article
title: Turing machines with few accepting computations and low sets for PP
zbMATH Open document ID: 0757.68056
DOI: 10.1016/0022-0000(92)90022-B
author: Johannes Köbler
author: Uwe Schöning
author: Jacobo Torán
author: Seinosuke Toda
published in: Journal of Computer and System Sciences
publication date: 1992-09-27T00:00:00Z
review text: Complexity classes, defined using the idea of bounding the number of accepting paths of a nondeterministic Turing machine, were introduced with the hope that perhaps they represent more tractable subclasses of the class \(NP\). The paper investigates some properties of the path- restricted class \(Few\), which includes also other known classes of this type, i.e. \(UP\) and \(FewP\). It is shown that for every language in this class there exists a polynomial time nondeterministic machine that has exactly \(f(x) + 1\) accepting paths for strings in the language, and \(f(x)\) accepting paths otherwise (for a polynomial time computable function \(f\)). This result is then used to prove that \(Few\) is low for the complexity classes \(PP\), \(\oplus P\), and \textit{exact counting}, i.e. an oracle from \(Few\) does not increase computational power of machines from these classes. Lowness for \(PP\) is shown also for sets from the class \(BPP\) and sparse sets in \(NP\).
Mathematics Subject Classification ID: 68Q15
Mathematics Subject Classification ID: 03D15
zbMATH DE Number: 58809
zbMATH Keywords: low sets
zbMATH Keywords: relativization
zbMATH Keywords: path restricted nondeterministic polynomial time machines
reviewed by: Jozef Vyskoč
MaRDI profile type: Publication
cites work: The polynomial-time hierarchy and sparse oracles
cites work: Quantitative Relativizations of Complexity Classes
cites work: On the power of parity polynomial time
cites work: Computational Complexity of Probabilistic Turing Machines
cites work: On Circuit-Size Complexity and the Low Hierarchy in NP
cites work: Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis
cites work: Q4743737
cites work: A low and a high hierarchy within NP
cites work: Complexity of Presburger arithmetic with fixed quantifier dimension
cites work: Restricted relativizations of probabilistic polynomial time
cites work: Relative complexity of checking and evaluating
cites work: The complexity of computing the permanent
cites work: The complexity of combinatorial problems with succinct input representation
cites work: A decisive characterization of BPP
full work available at URL: 0022-0000(92)90022-b
OpenAlex ID: W2178192088
description: scientific article; zbMATH DE number 58809