scientific article; zbMATH DE number 3984573

MaRDI QIDQ3747725zbMATH OpenFDO

Authors Eric Allender

Publication date 1986

zbMATH Keywords

DLOGFNPNCone-way functionsP-printable setsP-uniform circuit complexitypolynomial timesparse sets is Ptally language

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• P-Printable Sets
• On polynomial time one-truth-table reducibility to a sparse set
• On Sparse Complete Sets
• On the Computational Complexity of Small Descriptions
• Self-P-Printability and Polynomial Time Turing Equivalence to a Tally Set

Cited in

(32)

• On sparse oracles separating feasible complexity classes
• Unambiguous computations and locally definable acceptance types
• On polynomial time one-truth-table reducibility to a sparse set
• On the power of enumerative counting
• A note on sparse sets and the polynomial-time hierarchy
• Creating strong, total, commutative, associative one-way functions from any one-way function in complexity theory
• Gap-definable counting classes
• Non-deterministic communication complexity with few witnesses
• Scalability and the isomorphism problem
• On characterizing the existence of partial one-way permutations
• Enumerative counting is hard
• On the power of unambiguity in log-space
• The complexity of irredundant sets parameterized by size
• Quantum and classical complexity classes: Separations, collapses, and closure properties
• If P \(\neq\) NP then some strongly noninvertible functions are invertible
• Revisiting a result of Ko
• Characterizations and existence of easy sets without hard subsets
• Sparse and Lopsided Set Disjointness via Information Theory
• On polynomial-time truth-table reducibility of intractable sets to P-selective sets
• scientific article; zbMATH DE number 4106273 (Why is no real title available?)
• Structure and importance of logspace-MOD class
• scientific article; zbMATH DE number 1332663 (Why is no real title available?)
• scientific article; zbMATH DE number 1072529 (Why is no real title available?)
• scientific article; zbMATH DE number 1107624 (Why is no real title available?)
• On sets bounded truth-table reducible to P-selective sets
• The Untold Story of $$\mathsf {SBP}$$
• On the power of parity polynomial time
• Counting classes: Thresholds, parity, mods, and fewness
• Unambiguity and fewness for nonuniform families of polynomial-size nondeterministic finite automata
• Impossibilities in succinct arguments: black-box extraction and more
• Effective entropies and data compression
• Relative complexity of evaluating the optimum cost and constructing the optimum for maximization problems

This page was built for publication:

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