Complete distributional problems, hard languages, and resource-bounded measure

DOI10.1016/S0304-3975(99)00295-9zbMATH Open0947.68085OpenAlexW2049843410MaRDI QIDQ1575682FDOQ1575682

Authors: Aduri Pavan, Alan L. Selman 

Publication date: 21 August 2000

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0304-3975(99)00295-9

Recommendations

• Distributionally hard languages
• On the theory of average case complexity
• Complexity of distributions and average-case hardness

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Cites Work

• On the Computational Complexity of Algorithms
• Almost everywhere high nonuniform complexity
• Cook versus Karp-Levin: Separating completeness notions if NP is not small
• Title not available (Why is that?)
• A note on almost-everywhere-complex sets and separating deterministic- time-complexity classes
• On the theory of average case complexity
• Average case completeness
• Average Case Complete Problems
• On the definitions of some complexity classes of real numbers
• Computation times of NP sets of different densities
• Sparse sets in NP-P: EXPTIME versus NEXPTIME
• Almost every set in exponential time is P-bi-immune
• On the NP-isomorphism problem with respect to random instances
• Title not available (Why is that?)
• Fine Separation of Average-Time Complexity Classes
• P-Printable Sets
• Bi-immune sets for complexity classes
• Matrix Transformation Is Complete for the Average Case
• Title not available (Why is that?)
• Reductions do not preserve fast convergence rates in average time

Cited In (3)

• Complexity of distributions and average-case hardness
• The size of SPP
• Distributionally hard languages

This page was built for publication: Complete distributional problems, hard languages, and resource-bounded measure

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