Locating \(P\)/poly optimally in the extended low hierarchy
type: Item
instance of: scholarly article
title: Locating \(P\)/poly optimally in the extended low hierarchy
zbMATH Open document ID: 0834.68032
DOI: 10.1016/0304-3975(94)00016-6
published in: Theoretical Computer Science
publication date: 1996-03-18T00:00:00Z
Mathematics Subject Classification ID: 68Q15
zbMATH DE Number: 708700
zbMATH Keywords: lower bounds
zbMATH Keywords: low hierarchy
author: Johannes Köbler
MaRDI profile type: Publication
full work available at URL: 0304-3975(94)00016-6
OpenAlex ID: W2067811682
cites work: Lower bounds for the low hierarchy
cites work: Queries and concept learning
cites work: Sparse Sets, Lowness and Highness
cites work: Sets with small generalized Kolmogorov complexity
cites work: Q3996675
cites work: Bounded queries to SAT and the Boolean hierarchy
cites work: On Isomorphisms and Density of $NP$ and Other Complete Sets
cites work: Tally languages and complexity classes
cites work: SPARSE Reduces Conjunctively to TALLY
cites work: On truth-table reducibility to SAT
cites work: Universal classes of hash functions
cites work: Complexity classes between $\Theta _k^P$ and $\Delta _k^P$
cites work: Strong and robustly strong polynomial-time reducibilities to sparse sets
cites work: On sparse sets in NP-P
cites work: Computation times of NP sets of different densities
cites work: \(P^{NP[O(\log n)]}\) and sparse turing-complete sets for NP
cites work: Nonuniform proof systems: A new framework to describe nonuniform and probabilistic complexity classes
cites work: On Circuit-Size Complexity and the Low Hierarchy in NP
cites work: On counting and approximation
cites work: A comparison of polynomial time reducibilities
cites work: Strong nondeterministic polynomial-time reducibilities
cites work: UP and the low and high hierarchies: A relativized separation
cites work: Q3798240
cites work: Every Prime Has a Succinct Certificate
cites work: A low and a high hierarchy within NP
cites work: Complexity of Presburger arithmetic with fixed quantifier dimension
cites work: Complete sets and closeness to complexity classes
cites work: Graph isomorphism is in the low hierarchy
cites work: P-selective sets, tally languages, and the behavior of polynomial time reducibilities onNP
cites work: The extended low hierarchy is an infinite hierarchy
cites work: The polynomial-time hierarchy
cites work: On Approximation Algorithms for # P
cites work: The complexity of computing the permanent
cites work: Bounded Query Classes
cites work: On the complexity of small description and related topics
cites work: Structural analysis of polynomial-time query learnability
cites work: Complete sets and the polynomial-time hierarchy
description: scientific article; zbMATH DE number 708700