Independence results about context-free languages and lower bounds (Q1071500): Difference between revisions

For every axiomatizable, sound formal system F there exist instances about context-free languages, lower bounds of computation and recursive oracles A for which $NP^ A\neq P^ A$ that are not provable in F for every recursive representation of these problems.

0 references

zbMATH Keywords

provability

0 references

recursive oracles

0 references

MaRDI profile type

MaRDI publication profile

0 references

cites work

Q4773298

0 references

Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question

0 references

On Isomorphisms and Density of $NP$ and Other Complete Sets

0 references

Q4198056

0 references

Arithmetical hierarchy and complexity of computation

0 references

0 references

0 references

0 references

0 references

On the Structure of Polynomial Time Reducibility

0 references

On the structure of sets in NP and other complexity classes

0 references

Q5573961

0 references

A uniform approach to obtain diagonal sets in complexity classes

0 references

Identifiers

zbMATH Open document ID

0586.68029

0 references

DOI

10.1016/0020-0190(85)90026-2

0 references

Mathematics Subject Classification ID

0 references

0 references

0 references

0 references

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:1071500

@@ Property / OpenAlex ID @@
-W2085310804
@@ Property / OpenAlex ID: W2085310804 / rank @@
-Normal rank
@@ Property / OpenAlex ID @@
+W2085310804
@@ Property / OpenAlex ID: W2085310804 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4773298
@@ Property / cites work: Q4773298 / rank @@
+Normal rank
@@ Property / cites work @@
+Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
+Normal rank
@@ Property / cites work @@
+On Isomorphisms and Density of $NP$ and Other Complete Sets
+Normal rank
@@ Property / cites work @@
+Q4198056
@@ Property / cites work: Q4198056 / rank @@
+Normal rank
@@ Property / cites work @@
+Arithmetical hierarchy and complexity of computation
+Normal rank
@@ Property / cites work @@
+Q5583856
@@ Property / cites work: Q5583856 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4162663
@@ Property / cites work: Q4162663 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4197341
@@ Property / cites work: Q4197341 / rank @@
+Normal rank
@@ Property / cites work @@
+Q3676130
@@ Property / cites work: Q3676130 / rank @@
+Normal rank
@@ Property / cites work @@
+On the Structure of Polynomial Time Reducibility
@@ Property / cites work: On the Structure of Polynomial Time Reducibility / rank @@
+Normal rank
@@ Property / cites work @@
+On the structure of sets in NP and other complexity classes
+Normal rank
@@ Property / cites work @@
+Q5573961
@@ Property / cites work: Q5573961 / rank @@
+Normal rank
@@ Property / cites work @@
+A uniform approach to obtain diagonal sets in complexity classes
+Normal rank