No NP problems averaging over ranking of distributions are harder

DOI10.1016/S0304-3975(96)00272-1zbMath0912.68042MaRDI QIDQ1391309

Jie Wang, Jay Belanger

Publication date: 22 July 1998

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

zbMATH Keywords

average polynomial time\(T\) time on average

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Backtrack: An O(1) expected time algorithm for the graph coloring problem
• Average case completeness
• On average time hierarchies
• On the NP-isomorphism problem with respect to random instances
• Randomizing Reductions of Search Problems
• Average Case Complete Problems
• Expected Computation Time for Hamiltonian Path problem
• Probability with Martingales
• On Isomorphisms and Density of $NP$ and Other Complete Sets
• Matrix Transformation Is Complete for the Average Case
• Fine separation of average time complexity classes
• Constant time factors do matter

This page was built for publication: No NP problems averaging over ranking of distributions are harder