High probable polynomial time algorithm for NP-hard problems?

Many NP-complete or NP-hard problems are addressed under the assumption that the problem instances are uniformly distributed. However, it is not true for real world applications. One example is the SAT problem. Randomly generated SAT problems are greatly different from industry collected SAT problems. The solvers behave quite different.

I am thinking about an approximation scheme that given an unknown distribution $D$ over the problem instances, there exists a polynomial time algorithm $A$ that solves the problems drawn from $D$ successfully with a probability $1-\eta$. $\eta$ somehow relates to the divergence between the $D$ and the random distribution.

Furthermore, if we have samples from $D$, we can estimate $A$, and address the sample complexity and the consistency issue.

I wonder whether such a scheme already exists or not. If so, what is the name and what are the milestones?

• “Many NP-complete or NP-hard problems are addressed under the assumption that the problem instances are uniformly distributed.” I have difficulty understanding the meaning of this sentence. Are you saying that some (many?) NP-complete problems are known to be easy on average, or that some (many?) problems are known to be hard on average, or something else? Aug 30 '10 at 21:31
• Taking the kSAT as an example, you randomly generate 10,000 kSAT problems (literals and clauses), then apply several solvers to determine if they are Satisfiable. The literals and clauses form a problem space. The conventional algorithm theory concerns about the worst case running time for the entire problem space no matter if it is exact or approximate.
– miao
Sep 7 '10 at 18:05
• However, we never look at the distribution of problem instances on the problem space. In real world, the distribution of problem instances are quite different than randomly generated ones. Therefore, prioritizing the algorithm operations according to the real distribution might produce a Poly time performance.
– miao
Sep 7 '10 at 18:14
• Are you looking for Smoothed Analysis? Aug 2 '12 at 15:12