Tally NP sets and easy census functions.
type: Item
instance of: scholarly article
title: Tally NP sets and easy census functions.
zbMATH Open document ID: 1046.68538
author: J. Goldsmith
author: Jörg Rothe
author: Ogihara, Mitsunori
published in: Information and Computation
publication date: 2003-01-14T00:00:00Z
Mathematics Subject Classification ID: 68Q15
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 03D15
zbMATH DE Number: 1853099
zbMATH Keywords: collapses of language
MaRDI profile type: Publication
full work available at URL: inco.1999.2810
OpenAlex ID: W2015665482
cites work: Limitations of the upward separation technique
cites work: P-Printable Sets
cites work: The polynomial-time hierarchy and sparse oracles
cites work: Q4293543
cites work: Counting classes: Thresholds, parity, mods, and fewness
cites work: On Isomorphisms and Density of $NP$ and Other Complete Sets
cites work: Tally languages and complexity classes
cites work: Enumerative counting is hard
cites work: On the power of parity polynomial time
cites work: A note on enumerative counting
cites work: Gap-definable counting classes
cites work: Parity, circuits, and the polynomial-time hierarchy
cites work: Scalability and the isomorphism problem
cites work: Computational Complexity of Probabilistic Turing Machines
cites work: On the construction of parallel computers from various basis of Boolean functions
cites work: Compression and Ranking
cites work: On sparse sets in NP-P
cites work: The strong exponential hierarchy collapses
cites work: Relations among MOD-classes
cites work: A Downward Collapse within the Polynomial Hierarchy
cites work: Sparse sets in NP-P: EXPTIME versus NEXPTIME
cites work: Defying upward and downward separation
cites work: Boolean operations, joins, and the extended low hierarchy
cites work: On the complexity of ranking
cites work: Unambiguous Computation: Boolean Hierarchies and Sparse Turing-Complete Sets
cites work: Easy sets and hard certificate schemes
cites work: Q3862379
cites work: Computation times of NP sets of different densities
cites work: Q4526985
cites work: Relativized Polynomial Time Hierarchies Having Exactly K Levels
cites work: On Circuit-Size Complexity and the Low Hierarchy in NP
cites work: On counting and approximation
cites work: Turing machines with few accepting computations and low sets for PP
cites work: BPP and the polynomial hierarchy
cites work: On Restricting the Size of Oracles Compared with Restricting Access to Oracles
cites work: Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis
cites work: A complexity theory for feasible closure properties
cites work: Q4298260
cites work: Q4743737
cites work: Upward separation for FewP and related classes
cites work: A low and a high hierarchy within NP
cites work: Graph isomorphism is in the low hierarchy
cites work: The polynomial-time hierarchy
cites work: Counting Classes are at Least as Hard as the Polynomial-Time Hierarchy
cites work: PP is as Hard as the Polynomial-Time Hierarchy
cites work: Relative complexity of checking and evaluating
cites work: The complexity of computing the permanent
cites work: The Complexity of Enumeration and Reliability Problems
cites work: Q3140234
DOI: 10.1006/INCO.1999.2810
description: scientific article; zbMATH DE number 1853099