P-Printable Sets
From MaRDI portal
Publication:4732106
DOI10.1137/0217075zbMath0682.68039OpenAlexW2081902982MaRDI QIDQ4732106
Roy S. Rubinstein, Eric W. 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
computational complexitydata compressionKolmogorov complexitysparse setstally languageAuxPDAsP-isomorphisms
Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15) Other degrees and reducibilities in computability and recursion theory (03D30)
Related Items
A taxonomy of complexity classes of functions, NL-printable sets and nondeterministic Kolmogorov complexity, Scalability and the isomorphism problem, Measure on \(P\): Strength of the notion, Tight lower bounds on the ambiguity of strong, total, associative, one-way functions, Limitations of the upward separation technique, Degrees and reducibilities of easy tally sets, Unambiguity and fewness for nonuniform families of polynomial-size nondeterministic finite automata, Kolmogorov complexity and degrees of tally sets, On the complexity of ranking, Isolation, matching, and counting uniform and nonuniform upper bounds, On sets polynomially enumerable by iteration, Fault-tolerance and complexity (Extended abstract), Enforcing and defying associativity, commutativity, totality, and strong noninvertibility for worst-case one-way functions, On polynomial-time Turing and many-one completeness in PSPACE, Polynomial-time compression, If not empty, NP-P is topologically large, On the power of parity polynomial time, Nondeterminisic sublinear time has measure 0 in P, Circuit size relative to pseudorandom oracles, NL-printable sets and Nondeterministic Kolmogorov Complexity, Quantum and classical complexity classes: Separations, collapses, and closure properties, Lower bounds and the hardness of counting properties, Dimension, entropy rates, and compression, Reducibilities on tally and sparse sets, If P \(\neq\) NP then some strongly noninvertible functions are invertible, Some consequences of the existnce of pseudorandom generators, Complete distributional problems, hard languages, and resource-bounded measure, A second step towards complexity-theoretic analogs of Rice's Theorem, Tally NP sets and easy census functions., Sparse sets and collapse of complexity classes, Restrictive Acceptance Suffices for Equivalence Problems, Kolmogorov characterizations of complexity classes, Quasi-injective reductions, On characterizing the existence of partial one-way permutations, The complexity of computing maximal word functions
