Strong Hardness Preserving Reduction from a P-Samplable Distribution to the Uniform Distribution for NP-Search Problems.
Akinori KawachiOsamu WatanabePublished in: Electron. Colloquium Comput. Complex. (2009)
Keyphrases
- uniform distribution
- search problems
- learning dnf
- uniformly distributed
- agnostic learning
- pac learnable
- search algorithm
- orders of magnitude
- pac learning
- boolean functions
- heuristic search
- np complete
- random samples
- computational complexity
- search strategies
- random instances
- membership queries
- np hard
- monotone boolean functions
- constraint satisfaction problems
- search space
- phase transition
- learning theory
- pac learning model
- evolutionary algorithm
- search methods
- statistical queries
- dnf formulas
- learning problems
- term dnf
- information retrieval
- machine learning