scientific article
From MaRDI portal
Publication:3747725
zbMath0608.68035MaRDI QIDQ3747725
Publication date: 1986
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
polynomial timeone-way functionsNCDLOGtally languageP-uniform circuit complexityFNPP-printable setssparse sets is P
Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15)
Related Items (24)
The Untold Story of $$\mathsf {SBP}$$ ⋮ Revisiting a result of Ko ⋮ Non-deterministic communication complexity with few witnesses ⋮ Scalability and the isomorphism problem ⋮ On sparse oracles separating feasible complexity classes ⋮ Structure and importance of logspace-MOD class ⋮ On polynomial-time truth-table reducibility of intractable sets to P-selective sets ⋮ Unambiguous computations and locally definable acceptance types ⋮ On the power of unambiguity in log-space ⋮ On the power of parity polynomial time ⋮ Unambiguity and fewness for nonuniform families of polynomial-size nondeterministic finite automata ⋮ Impossibilities in succinct arguments: black-box extraction and more ⋮ Relative complexity of evaluating the optimum cost and constructing the optimum for maximization problems ⋮ On polynomial time one-truth-table reducibility to a sparse set ⋮ On the power of enumerative counting ⋮ Counting classes: Thresholds, parity, mods, and fewness ⋮ Quantum and classical complexity classes: Separations, collapses, and closure properties ⋮ If P \(\neq\) NP then some strongly noninvertible functions are invertible ⋮ Effective entropies and data compression ⋮ On sets bounded truth-table reducible to $P$-selective sets ⋮ Enumerative counting is hard ⋮ Creating strong, total, commutative, associative one-way functions from any one-way function in complexity theory ⋮ On characterizing the existence of partial one-way permutations ⋮ Gap-definable counting classes
This page was built for publication:
