Nonuniform proof systems: A new framework to describe nonuniform and probabilistic complexity classes

DOI10.1016/0304-3975(91)90185-5zbMATH Open0733.68031OpenAlexW2021218132MaRDI QIDQ809600FDOQ809600

Authors: Jürgen Kämper 

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

Recommendations

• scientific article; zbMATH DE number 4090801
• Instruction sequence based non-uniform complexity classes
• Different approaches to proof systems
• Nondeterministic Instance Complexity and Proof Systems with Advice
• Nonuniform reductions and NP-completeness

zbMATH Keywords

nonuniform complexitylownessadvice classes

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Cites Work

• Alternation
• On helping by robust oracle machines
• The polynomial-time hierarchy
• Computational Complexity of Probabilistic Turing Machines
• P-selective sets, tally languages, and the behavior of polynomial time reducibilities onNP
• BPP and the polynomial hierarchy
• A decisive characterization of BPP
• Some consequences of non-uniform conditions on uniform classes
• On self-reducibility and weak P-selectivity
• A low and a high hierarchy within NP
• Strong nondeterministic polynomial-time reducibilities
• Title not available (Why is that?)
• Title not available (Why is that?)
• On Certain Polynomial-Time Truth-Table Reducibilities of Complete Sets to Sparse Sets
• Title not available (Why is that?)
• Reductions on NP and p-selective sets
• Some observations on the probabilistic algorithms and NP-hard problems
• On Circuit-Size Complexity and the Low Hierarchy in NP
• Title not available (Why is that?)
• Sparse Sets, Lowness and Highness
• Complexity of Presburger arithmetic with fixed quantifier dimension
• Title not available (Why is that?)
• Title not available (Why is that?)
• On small generators
• Nonuniform proof systems: A new framework to describe nonuniform and probabilistic complexity classes

Cited In (9)

• Instruction sequence based non-uniform complexity classes
• Different approaches to proof systems
• Separation of complexity classes in Koiran's weak model
• New collapse consequences of NP having small circuits
• Locating \(P\)/poly optimally in the extended low hierarchy
• Title not available (Why is that?)
• Competing provers yield improved Karp-Lipton collapse results
• Title not available (Why is that?)
• 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)