Rankable distributions do not provide harder instances than uniform distributions

DOI10.1007/bfb0030860zbMath1527.68076MaRDI QIDQ6085735

Jay Belanger, Jie Wang

Publication date: 12 December 2023

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Cites Work

• Average case completeness
• On the theory of average case complexity
• Average case complexity under the universal distribution equals worst- case complexity
• 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
• 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
• On the Computational Complexity of Algorithms
• The NP-completeness column: An ongoing guide
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Rankable distributions do not provide harder instances than uniform distributions