Polynomial-time compression (Q1198955): Difference between revisions

@@ Property / cites work @@
+P-Printable Sets
@@ Property / cites work: P-Printable Sets / rank @@
+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 @@
+On Isomorphisms and Density of $NP$ and Other Complete Sets
+Normal rank
@@ Property / cites work @@
+Bounded query machines: on NP and PSPACE
@@ Property / cites work: Bounded query machines: on NP and PSPACE / rank @@
+Normal rank
@@ Property / cites work @@
+Bounded query machines: on NP( ) and NPQUERY( )
@@ Property / cites work: Bounded query machines: on NP( ) and NPQUERY( ) / rank @@
+Normal rank
@@ Property / cites work @@
+Dynamic Perfect Hashing: Upper and Lower Bounds
@@ Property / cites work: Dynamic Perfect Hashing: Upper and Lower Bounds / rank @@
+Normal rank
@@ Property / cites work @@
+Q4198056
@@ Property / cites work: Q4198056 / rank @@
+Normal rank
@@ Property / cites work @@
+Complexity Measures for Public-Key Cryptosystems
@@ Property / cites work: Complexity Measures for Public-Key Cryptosystems / rank @@
+Normal rank
@@ Property / cites work @@
+Sparse sets in NP-P: EXPTIME versus NEXPTIME
@@ Property / cites work: Sparse sets in NP-P: EXPTIME versus NEXPTIME / rank @@
+Normal rank
@@ Property / cites work @@
+Computation times of NP sets of different densities
+Normal rank
@@ Property / cites work @@
+The strong exponential hierarchy collapses
@@ Property / cites work: The strong exponential hierarchy collapses / rank @@
+Normal rank
@@ Property / cites work @@
+Q4201936
@@ Property / cites work: Q4201936 / rank @@
+Normal rank
@@ Property / cites work @@
+On sets polynomially enumerable by iteration
@@ Property / cites work: On sets polynomially enumerable by iteration / rank @@
+Normal rank
@@ Property / cites work @@
+Relating Equivalence and Reducibility to Sparse Sets
+Normal rank
@@ Property / cites work @@
+On the complexity of ranking
@@ Property / cites work: On the complexity of ranking / rank @@
+Normal rank
@@ Property / cites work @@
+Oracle-dependent properties of the lattice of NP sets
+Normal rank
@@ Property / cites work @@
+The complexity of ranking simple languages
@@ Property / cites work: The complexity of ranking simple languages / rank @@
+Normal rank
@@ Property / cites work @@
+Some remarks on witness functions for nonpolynomial and noncomplete sets in NP
+Normal rank
@@ Property / cites work @@
+Q4057549
@@ Property / cites work: Q4057549 / rank @@
+Normal rank
@@ Property / cites work @@
+Reductions among polynomial isomorphism types
@@ Property / cites work: Reductions among polynomial isomorphism types / rank @@
+Normal rank
@@ Property / cites work @@
+The complexity of facets (and some facets of complexity)
+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 @@
+Perfect hashing functions
@@ Property / cites work: Perfect hashing functions / rank @@
+Normal rank
@@ Property / cites work @@
+The polynomial-time hierarchy
@@ Property / cites work: The polynomial-time hierarchy / rank @@
+Normal rank
@@ Property / cites work @@
+Query complexity, or why is it difficult to separate \(NP^ A\cap coNP^ A\) from \(P^ A\) by random oracles A?
+Normal rank
@@ Property / cites work @@
+Relative complexity of checking and evaluating
@@ Property / cites work: Relative complexity of checking and evaluating / rank @@
+Normal rank
@@ Property / cites work @@
+The Complexity of Enumeration and Reliability Problems
+Normal rank