Relativizing small complexity classes and their theories (Q260396): Difference between revisions

Latest revision as of 15:17, 11 July 2024

scientific article; zbMATH DE number 5523406

Relativizing Small Complexity Classes and Their Theories

Language	Label	Description	Also known as
English	Relativizing small complexity classes and their theories	scientific article; zbMATH DE number 5523406	Relativizing Small Complexity Classes and Their Theories

Statements

instance of

scholarly article

0 references

title

Relativizing small complexity classes and their theories (English)

0 references

Relativizing Small Complexity Classes and Their Theories (English)

0 references

0 references

0 references

Computational Complexity

0 references

Computer Science Logic

0 references

publication date

21 March 2016

0 references

5 March 2009

0 references

full work available at URL

https://arxiv.org/abs/1204.5508

0 references

zbMATH Keywords

complexity classes

0 references

relativized classes

0 references

proof complexity

0 references

logical theories

0 references

MaRDI profile type

MaRDI publication profile

0 references

cites work

Space-bounded hierarchies and probabilistic computations

0 references

Relativizing small complexity classes and their theories

0 references

On uniformity within \(NC^ 1\)

0 references

Q4721649

0 references

On uniform circuit complexity

0 references

A taxonomy of problems with fast parallel algorithms

0 references

Q4227581

0 references

Q4856172

0 references

Relativization of questions about log space computability

0 references

Theories for TC0 and Other Small Complexity Classes

0 references

Separations of theories in weak bounded arithmetic

0 references

RelativizedNC

0 references

A measure of relativized space which is faithful with respect to depth

0 references

Notes on polynomially bounded arithmetic

0 references

Identifiers

zbMATH Open document ID

1336.68084

0 references

1179.68059

0 references

DOI

10.1007/s00037-015-0113-8

0 references

10.1007/978-3-540-74915-8_29

0 references

Mathematics Subject Classification ID

0 references

0 references

0 references

0 references

0 references

0 references

0 references

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:260396

@@ Property / cites work @@
+Space-bounded hierarchies and probabilistic computations
+Normal rank
@@ Property / cites work @@
+Relativizing small complexity classes and their theories
+Normal rank
@@ Property / cites work @@
+On uniformity within \(NC^ 1\)
@@ Property / cites work: On uniformity within \(NC^ 1\) / rank @@
+Normal rank
@@ Property / cites work @@
+Q4721649
@@ Property / cites work: Q4721649 / rank @@
+Normal rank
@@ Property / cites work @@
+On uniform circuit complexity
@@ Property / cites work: On uniform circuit complexity / rank @@
+Normal rank
@@ Property / cites work @@
+A taxonomy of problems with fast parallel algorithms
+Normal rank
@@ Property / cites work @@
+Q4227581
@@ Property / cites work: Q4227581 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4856172
@@ Property / cites work: Q4856172 / rank @@
+Normal rank
@@ Property / cites work @@
+Relativization of questions about log space computability
+Normal rank
@@ Property / cites work @@
+Theories for TC0 and Other Small Complexity Classes
+Normal rank
@@ Property / cites work @@
+Separations of theories in weak bounded arithmetic
+Normal rank
@@ Property / cites work @@
+RelativizedNC
@@ Property / cites work: RelativizedNC / rank @@
+Normal rank
@@ Property / cites work @@
+A measure of relativized space which is faithful with respect to depth
+Normal rank
@@ Property / cites work @@
+Notes on polynomially bounded arithmetic
@@ Property / cites work: Notes on polynomially bounded arithmetic / rank @@
+Normal rank