Polynomial-time compression
From MaRDI portal
Recommendations
- On the optimal compression of sets in PSPACE
- On optimal language compression for sets in PSPACE/poly
- On the compressibility of \(\mathcal{NP}\) instances and cryptographic applications
- On Certain Polynomial-Time Truth-Table Reducibilities of Complete Sets to Sparse Sets
- Infeasibility of instance compression and succinct PCPs for NP
Cites work
- scientific article; zbMATH DE number 3473265 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 403952 (Why is no real title available?)
- A low and a high hierarchy within NP
- Bounded query machines: on NP and PSPACE
- Bounded query machines: on NP( ) and NPQUERY( )
- Complexity Measures for Public-Key Cryptosystems
- Computation times of NP sets of different densities
- Dynamic Perfect Hashing: Upper and Lower Bounds
- On Isomorphisms and Density of $NP$ and Other Complete Sets
- On sets polynomially enumerable by iteration
- On the complexity of ranking
- Oracle-dependent properties of the lattice of NP sets
- P-Printable Sets
- Perfect hashing functions
- Query complexity, or why is it difficult to separate NP^ A coNP^ A from P^ A by random oracles A?
- Reductions among polynomial isomorphism types
- Relating Equivalence and Reducibility to Sparse Sets
- Relative complexity of checking and evaluating
- Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
- Some remarks on witness functions for nonpolynomial and noncomplete sets in NP
- Sparse sets in NP-P: EXPTIME versus NEXPTIME
- The Complexity of Enumeration and Reliability Problems
- The complexity of facets (and some facets of complexity)
- The complexity of ranking simple languages
- The polynomial-time hierarchy
- The strong exponential hierarchy collapses
Cited in
(12)- Avoiding simplicity is complex
- scientific article; zbMATH DE number 403952 (Why is no real title available?)
- Polynomial-time axioms of choice and polynomial-time cardinality
- On optimal language compression for sets in PSPACE/poly
- On the compressibility of \(\mathcal{NP}\) instances and cryptographic applications
- Closure and nonclosure properties of the classes of compressible and rankable sets
- On the optimal compression of sets in PSPACE
- scientific article; zbMATH DE number 3902038 (Why is no real title available?)
- Resource-bounded Kolmogorov complexity revisited
- Scalability and the isomorphism problem
- Recursion-theoretic ranking and compression
- Characterizing the existence of one-way permutations
This page was built for publication: Polynomial-time compression
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1198955)
