The probabilistic analysis of NP-hard problems has demonstrated that they are all not equally hard to solve in practice; for example, Hamiltonian paths are easy to find on the average, while random graph coloring still resists attack. This project considers the class DNP (the class of NP problems with input distributions) defined by Levin, and examine the issue of whether DNP = NP? While several DNP-complete problems have been identified, none is a natural problem under a natural distribution. This work proves a result of the type: satisfiability or graph coloring under a uniform distribution is DNP-hard. In particular, it demonstrates that random 3-SAT formulas exhibit a sharp threshold phenomena with respect to the ratio of the number of clauses to the number of variables and more significantly, to show that the random instances of this problem are provably intractable when the ratio is at the threshold value. The general question demonstrates that problems which admit a sharp threshold behavior are hard to solve in the immediate neighborhood of the threshold value. Another problem considered is that of relating DNP-hardness to NP-hardness, or perhaps some weaker intractability assumption. For example, for some class of problems, does an efficient average-case solution imply an unlikely outcome such as P = NP?
