Nonuniform proof systems: A new framework to describe nonuniform and probabilistic complexity classes (Q809600): Difference between revisions

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.

0 references

zbMATH Keywords

nonuniform complexity

0 references

advice classes

0 references

lowness

0 references

MaRDI profile type

Publication

0 references

full work available at URL

https://doi.org/10.1016/0304-3975(91)90185-5

0 references

cites work

Q3217605

0 references

Q3765251

0 references

Sparse Sets, Lowness and Highness

0 references

Q3692867

0 references

Alternation

0 references

Computational Complexity of Probabilistic Turing Machines

0 references

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

0 references

On self-reducibility and weak P-selectivity

0 references

Some observations on the probabilistic algorithms and NP-hard problems

0 references

On Circuit-Size Complexity and the Low Hierarchy in NP

0 references

On helping by robust oracle machines

0 references

BPP and the polynomial hierarchy

0 references

Strong nondeterministic polynomial-time reducibilities

0 references

A low and a high hierarchy within NP

0 references

On small generators

0 references

Q3694694

0 references

Complexity of Presburger arithmetic with fixed quantifier dimension

0 references

Q3758245

0 references

P-selective sets, tally languages, and the behavior of polynomial time reducibilities onNP

0 references

Reductions on NP and p-selective sets

0 references

The polynomial-time hierarchy

0 references

Some consequences of non-uniform conditions on uniform classes

0 references

On Certain Polynomial-Time Truth-Table Reducibilities of Complete Sets to Sparse Sets

0 references

Q3768891

0 references

A decisive characterization of BPP

0 references

Identifiers

zbMATH Open document ID

0733.68031

0 references

DOI

10.1016/0304-3975(91)90185-5

0 references

Mathematics Subject Classification ID

0 references

0 references

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:809600

@@ Property / full work available at URL @@
+https://doi.org/10.1016/0304-3975(91)90185-5
+Normal rank
@@ Property / OpenAlex ID @@
+W2021218132
@@ Property / OpenAlex ID: W2021218132 / rank @@
+Normal rank
@@ Property / cites work @@
+Q3217605
@@ Property / cites work: Q3217605 / rank @@
+Normal rank
@@ Property / cites work @@
+Q3765251
@@ Property / cites work: Q3765251 / rank @@
+Normal rank
@@ Property / cites work @@
+Sparse Sets, Lowness and Highness
@@ Property / cites work: Sparse Sets, Lowness and Highness / rank @@
+Normal rank
@@ Property / cites work @@
+Q3692867
@@ Property / cites work: Q3692867 / rank @@
+Normal rank
@@ Property / cites work @@
+Alternation
@@ Property / cites work: Alternation / rank @@
+Normal rank
@@ Property / cites work @@
+Computational Complexity of Probabilistic Turing Machines
+Normal rank
@@ Property / cites work @@
+Nonuniform proof systems: A new framework to describe nonuniform and probabilistic complexity classes
+Normal rank
@@ Property / cites work @@
+On self-reducibility and weak P-selectivity
@@ Property / cites work: On self-reducibility and weak P-selectivity / rank @@
+Normal rank
@@ Property / cites work @@
+Some observations on the probabilistic algorithms and NP-hard problems
+Normal rank
@@ Property / cites work @@
+On Circuit-Size Complexity and the Low Hierarchy in NP
+Normal rank
@@ Property / cites work @@
+On helping by robust oracle machines
@@ Property / cites work: On helping by robust oracle machines / rank @@
+Normal rank
@@ Property / cites work @@
+BPP and the polynomial hierarchy
@@ Property / cites work: BPP and the polynomial hierarchy / rank @@
+Normal rank
@@ Property / cites work @@
+Strong nondeterministic polynomial-time reducibilities
+Normal rank
@@ Property / cites work @@
+A low and a high hierarchy within NP
@@ Property / cites work: A low and a high hierarchy within NP / rank @@
+Normal rank
@@ Property / cites work @@
+On small generators
@@ Property / cites work: On small generators / rank @@
+Normal rank
@@ Property / cites work @@
+Q3694694
@@ Property / cites work: Q3694694 / rank @@
+Normal rank
@@ Property / cites work @@
+Complexity of Presburger arithmetic with fixed quantifier dimension
+Normal rank
@@ Property / cites work @@
+Q3758245
@@ Property / cites work: Q3758245 / rank @@
+Normal rank
@@ Property / cites work @@
+P-selective sets, tally languages, and the behavior of polynomial time reducibilities onNP
+Normal rank
@@ Property / cites work @@
+Reductions on NP and p-selective sets
@@ Property / cites work: Reductions on NP and p-selective sets / rank @@
+Normal rank
@@ Property / cites work @@
+The polynomial-time hierarchy
@@ Property / cites work: The polynomial-time hierarchy / rank @@
+Normal rank
@@ Property / cites work @@
+Some consequences of non-uniform conditions on uniform classes
+Normal rank
@@ Property / cites work @@
+On Certain Polynomial-Time Truth-Table Reducibilities of Complete Sets to Sparse Sets
+Normal rank
@@ Property / cites work @@
+Q3768891
@@ Property / cites work: Q3768891 / rank @@
+Normal rank
@@ Property / cites work @@
+A decisive characterization of BPP
@@ Property / cites work: A decisive characterization of BPP / rank @@
+Normal rank