Nonuniform proof systems: A new framework to describe nonuniform and probabilistic complexity classes
type: Item
instance of: scholarly article
title: Nonuniform proof systems: A new framework to describe nonuniform and probabilistic complexity classes
zbMATH Open document ID: 0733.68031
DOI: 10.1016/0304-3975(91)90185-5
author: Jürgen Kämper
published in: Theoretical Computer Science
publication date: 1991-01-01T00:00:00Z
review text: The concept of a nonuniform proof system, as a generalization of Karp/Lipton's advice classes, is introduced and studied. Many results from (nonuniform) complexity theory can thus be obtained in a unified framework. This includes certain results on probabilistic classes, lowness results, and collapsing results for the polynomial-time hierarchy.
Mathematics Subject Classification ID: 68Q15
zbMATH DE Number: 4213442
zbMATH Keywords: nonuniform complexity
zbMATH Keywords: advice classes
zbMATH Keywords: lowness
MaRDI profile type: Publication
full work available at URL: 0304-3975(91)90185-5
OpenAlex ID: W2021218132
cites work: Q3217605
cites work: Q3765251
cites work: Sparse Sets, Lowness and Highness
cites work: Q3692867
cites work: Alternation
cites work: Computational Complexity of Probabilistic Turing Machines
cites work: On self-reducibility and weak P-selectivity
cites work: Some observations on the probabilistic algorithms and NP-hard problems
cites work: On Circuit-Size Complexity and the Low Hierarchy in NP
cites work: On helping by robust oracle machines
cites work: BPP and the polynomial hierarchy
cites work: Strong nondeterministic polynomial-time reducibilities
cites work: A low and a high hierarchy within NP
cites work: On small generators
cites work: Q3694694
cites work: Complexity of Presburger arithmetic with fixed quantifier dimension
cites work: Q3758245
cites work: P-selective sets, tally languages, and the behavior of polynomial time reducibilities onNP
cites work: Reductions on NP and p-selective sets
cites work: The polynomial-time hierarchy
cites work: Some consequences of non-uniform conditions on uniform classes
cites work: On Certain Polynomial-Time Truth-Table Reducibilities of Complete Sets to Sparse Sets
cites work: Q3768891
cites work: A decisive characterization of BPP
description: scientific article; zbMATH DE number 4213442