|
|||||
|
|
Generalized juntas and NP-hard sets |
|
| Authors: | Gbor Erdlyi Lane A Hemaspaandra Jrg Rothe Holger Spakowski |
| Affiliation: | aInstitut für Informatik, Heinrich-Heine-Universität Düsseldorf, 40225 Düsseldorf, Germany;bDepartment of Computer Science, University of Rochester, Rochester, NY 14627, USA;cDepartment of Mathematics & Applied Mathematics, University of Cape Town, Rondebosch 7701, South Africa |
| Abstract: | 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. |
| Keywords: | NP-completeness Padding Junta distributions |
| 本文献已被 ScienceDirect 等数据库收录！ | |