P-Printable Sets

DOI10.1137/0217075MaRDI QIDQ4732106zbMATH OpenOpenAlexFDO

Authors Roy S. Rubinstein, Eric Allender

Publication date 1988

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/0217075

zbMATH Keywords

AuxPDAscomputational complexitydata compressionKolmogorov complexityP-isomorphismssparse setstally language

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Other degrees and reducibilities in computability and recursion theory (03D30) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Sets with small generalized Kolmogorov complexity
• Self-P-Printability and Polynomial Time Turing Equivalence to a Tally Set
• L-Printable Sets
• scientific article; zbMATH DE number 4079403
• Power from Random Strings

Cited in

(45)

• On sets polynomially enumerable by iteration
• On polynomial-time Turing and many-one completeness in PSPACE
• Polynomial-time compression
• Circuit size relative to pseudorandom oracles
• Quasi-injective reductions
• The complexity of computing maximal word functions
• A taxonomy of complexity classes of functions
• Scalability and the isomorphism problem
• Measure on P: Strength of the notion
• Complete distributional problems, hard languages, and resource-bounded measure
• A second step towards complexity-theoretic analogs of Rice's Theorem
• On characterizing the existence of partial one-way permutations
• Sets with small generalized Kolmogorov complexity
• Some consequences of the existnce of pseudorandom generators
• Tally NP sets and easy census functions.
• Sparse sets and collapse of complexity classes
• Isolation, matching, and counting uniform and nonuniform upper bounds
• Nondeterminisic sublinear time has measure 0 in P
• NL-printable sets and nondeterministic Kolmogorov complexity
• Quantum and classical complexity classes: Separations, collapses, and closure properties
• Dimension, entropy rates, and compression
• If P \(\neq\) NP then some strongly noninvertible functions are invertible
• Reducibilities on tally and sparse sets
• Limitations of the upward separation technique
• scientific article; zbMATH DE number 3974293 (Why is no real title available?)
• scientific article; zbMATH DE number 3984573 (Why is no real title available?)
• Self-P-Printability and Polynomial Time Turing Equivalence to a Tally Set
• L-Printable Sets
• Restrictive Acceptance Suffices for Equivalence Problems
• Fault-tolerance and complexity (extended abstract)
• NL-printable sets and nondeterministic Kolmogorov complexity
• Degrees and reducibilities of easy tally sets
• On the power of parity polynomial time
• Tight lower bounds on the ambiguity of strong, total, associative, one-way functions
• Unambiguity and fewness for nonuniform families of polynomial-size nondeterministic finite automata
• On the power of counting the total number of computation paths of NPTMs
• If not empty, NP-P is topologically large
• Gaps, ambiguity, and establishing complexity-class containments via iterative constant-setting
• Lower bounds and the hardness of counting properties
• An oracle with no up-complete sets, but NP = PSPACE
• The complexity of computing second solutions
• Kolmogorov characterizations of complexity classes
• Kolmogorov complexity and degrees of tally sets
• On the complexity of ranking
• Enforcing and defying associativity, commutativity, totality, and strong noninvertibility for worst-case one-way functions

This page was built for publication: P-Printable Sets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4732106)