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.

Authors

• Gábor Erdélyi University of Siegen
• Lane A. Hemaspaandra
• Jörg Rothe
• Holger Spakowski

Keywords

• NP-completeness
• Padding
• Junta distributions