Nonuniform proof systems: A new framework to describe nonuniform and probabilistic complexity classes
From MaRDI portal
(Redirected from Publication:809600)
Recommendations
Cites work
- scientific article; zbMATH DE number 3883613 (Why is no real title available?)
- scientific article; zbMATH DE number 3917710 (Why is no real title available?)
- scientific article; zbMATH DE number 3919821 (Why is no real title available?)
- scientific article; zbMATH DE number 4007728 (Why is no real title available?)
- scientific article; zbMATH DE number 4022646 (Why is no real title available?)
- scientific article; zbMATH DE number 4027449 (Why is no real title available?)
- A decisive characterization of BPP
- A low and a high hierarchy within NP
- Alternation
- BPP and the polynomial hierarchy
- Complexity of Presburger arithmetic with fixed quantifier dimension
- Computational Complexity of Probabilistic Turing Machines
- Nonuniform proof systems: A new framework to describe nonuniform and probabilistic complexity classes
- On Certain Polynomial-Time Truth-Table Reducibilities of Complete Sets to Sparse Sets
- On Circuit-Size Complexity and the Low Hierarchy in NP
- On helping by robust oracle machines
- On self-reducibility and weak P-selectivity
- On small generators
- P-selective sets, tally languages, and the behavior of polynomial time reducibilities onNP
- Reductions on NP and p-selective sets
- Some consequences of non-uniform conditions on uniform classes
- Some observations on the probabilistic algorithms and NP-hard problems
- Sparse Sets, Lowness and Highness
- Strong nondeterministic polynomial-time reducibilities
- The polynomial-time hierarchy
Cited in
(9)- Instruction sequence based non-uniform complexity classes
- Separation of complexity classes in Koiran's weak model
- Different approaches to proof systems
- New collapse consequences of NP having small circuits
- Locating \(P\)/poly optimally in the extended low hierarchy
- scientific article; zbMATH DE number 4090801 (Why is no real title available?)
- Competing provers yield improved Karp-Lipton collapse results
- scientific article; zbMATH DE number 951900 (Why is no real title available?)
- Nonuniform proof systems: A new framework to describe nonuniform and probabilistic complexity classes
This page was built for publication: Nonuniform proof systems: A new framework to describe nonuniform and probabilistic complexity classes
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q809600)
