Nonuniform proof systems: A new framework to describe nonuniform and probabilistic complexity classes
From MaRDI portal
Publication:809600
DOI10.1016/0304-3975(91)90185-5zbMath0733.68031OpenAlexW2021218132MaRDI QIDQ809600
Publication date: 1991
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0304-3975(91)90185-5
Related Items (5)
Separation of complexity classes in Koiran's weak model ⋮ Locating \(P\)/poly optimally in the extended low hierarchy ⋮ New collapse consequences of NP having small circuits ⋮ Competing provers yield improved Karp-Lipton collapse results ⋮ Nonuniform proof systems: A new framework to describe nonuniform and probabilistic complexity classes
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Some consequences of non-uniform conditions on uniform classes
- On small generators
- Nonuniform proof systems: A new framework to describe nonuniform and probabilistic complexity classes
- BPP and the polynomial hierarchy
- A low and a high hierarchy within NP
- On self-reducibility and weak P-selectivity
- Strong nondeterministic polynomial-time reducibilities
- On helping by robust oracle machines
- Some observations on the probabilistic algorithms and NP-hard problems
- Reductions on NP and p-selective sets
- The polynomial-time hierarchy
- Complexity of Presburger arithmetic with fixed quantifier dimension
- On Certain Polynomial-Time Truth-Table Reducibilities of Complete Sets to Sparse Sets
- On Circuit-Size Complexity and the Low Hierarchy in NP
- Sparse Sets, Lowness and Highness
- Alternation
- Computational Complexity of Probabilistic Turing Machines
- P-selective sets, tally languages, and the behavior of polynomial time reducibilities onNP
- A decisive characterization of BPP
This page was built for publication: Nonuniform proof systems: A new framework to describe nonuniform and probabilistic complexity classes
