Generalized juntas and NP-hard sets
We show that many NP-hard sets have heuristic polynomial-time algorithms with high probability weight of correctness with respect to generalizations of Procaccia and Rosenschein's junta distributions. (C) 2009 Elsevier B.V. All rights reserved.
junta distributions np-completeness padding