Some properties of sets tractable under every polynomial-time computable distribution
From MaRDI portal
Publication:1350351
DOI10.1016/0020-0190(95)00108-OzbMath0875.68537MaRDI QIDQ1350351
Publication date: 27 February 1997
Published in: Information Processing Letters (Search for Journal in Brave)
Related Items
Cites Work
- Unnamed Item
- A Turing machine time hierarchy
- Backtrack: An O(1) expected time algorithm for the graph coloring problem
- Computational complexity of real functions
- Average case completeness
- On the theory of average case complexity
- On the greedy algorithm for satisfiability
- Average case complexity under the universal distribution equals worst- case complexity
- Average Case Complete Problems
- Expected Computation Time for Hamiltonian Path problem
- The Complexity of Malign Measures
- The NP-completeness column: An ongoing guide