Some properties of sets tractable under every polynomial-time computable distribution

DOI10.1016/0020-0190(95)00108-OMaRDI QIDQ1350351zbMATH OpenFDO

Authors Rainer Schuler

Publication date 27 February 1997

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0190(95)00108-O

zbMATH Keywords

Average-case analysisComputational complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Recommendations

• On the theory of average case complexity
• scientific article; zbMATH DE number 512799
• scientific article; zbMATH DE number 512870

Cites work

• A Turing machine time hierarchy
• Average Case Complete Problems
• Average case completeness
• Average case complexity under the universal distribution equals worst- case complexity
• Backtrack: An O(1) expected time algorithm for the graph coloring problem
• Computational complexity of real functions
• Expected Computation Time for Hamiltonian Path problem
• scientific article; zbMATH DE number 512799 (Why is no real title available?)
• On the greedy algorithm for satisfiability
• On the theory of average case complexity
• The Complexity of Malign Measures
• The NP-completeness column: An ongoing guide

Cited in

(6)

• Polynomial time samplable distributions
• Average polynomial time is hard for exponential time under sn-reductions
• scientific article; zbMATH DE number 1222584 (Why is no real title available?)
• Average-case intractability vs. worst-case intractability
• Sets computable in polynomial time on average
• Structure in average case complexity

This page was built for publication: Some properties of sets tractable under every polynomial-time computable distribution

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