The relativized relationship between probabilistically checkable debate systems, IP and PSPACE (Q673812): Difference between revisions

@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / full work available at URL @@
+https://doi.org/10.1016/0020-0190(94)00185-2
+Normal rank
@@ Property / OpenAlex ID @@
+W2041566873
@@ Property / OpenAlex ID: W2041566873 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4230322
@@ Property / cites work: Q4230322 / rank @@
+Normal rank
@@ Property / cites work @@
+Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
+Normal rank
@@ Property / cites work @@
+Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
+Normal rank
@@ Property / cites work @@
+Relative to a Random Oracle<i>A</i>, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
+Normal rank
@@ Property / cites work @@
+The random oracle hypothesis is false
@@ Property / cites work: The random oracle hypothesis is false / rank @@
+Normal rank
@@ Property / cites work @@
+Probabilistically checkable debate systems and approximation algorithms for PSPACE-hard functions
+Normal rank
@@ Property / cites work @@
+Are there interactive protocols for co-NP languages?
+Normal rank
@@ Property / cites work @@
+The Knowledge Complexity of Interactive Proof Systems
+Normal rank
@@ Property / cites work @@
+Q4005200
@@ Property / cites work: Q4005200 / rank @@
+Normal rank
@@ Property / cites work @@
+Q3820009
@@ Property / cites work: Q3820009 / rank @@
+Normal rank
@@ Property / cites work @@
+On the Computational Complexity of Algorithms
@@ Property / cites work: On the Computational Complexity of Algorithms / rank @@
+Normal rank
@@ Property / cites work @@
+Q3663271
@@ Property / cites work: Q3663271 / rank @@
+Normal rank
@@ Property / cites work @@
+On the random oracle hypothesis
@@ Property / cites work: On the random oracle hypothesis / rank @@
+Normal rank
@@ Property / cites work @@
+Algebraic methods for interactive proof systems
@@ Property / cites work: Algebraic methods for interactive proof systems / rank @@
+Normal rank
@@ Property / cites work @@
+Q5541339
@@ Property / cites work: Q5541339 / rank @@
+Normal rank
@@ Property / cites work @@
+IP = PSPACE
@@ Property / cites work: IP = PSPACE / rank @@
+Normal rank
@@ Property / Wikidata QID @@
+Q127433722
@@ Property / Wikidata QID: Q127433722 / rank @@
+Normal rank
@@ links / mardi / name / links / mardi / name @@
+Publication:673812