Let us say that a language $L$ is P-density-close if there is a polynomial time algorithm that correctly decides $L$ on almost all inputs. In other words, there is an  $A\in$ P, such that $L\Delta A$ is vanishing, which means $$\lim_{n\rightarrow\infty} \frac{|(L\Delta A) \cap \{0,1\}^n|}{2^n}=0.$$It also means that on a uniform random input, the polytime algorithm for $A$ will give the correct answer for $L$ with probability approaching 1. Therefore, it makes sense to view $L$ almost easy.Note that $L\Delta A$ does not have to be sparse. For example, if it has  $2^{n/2}$ $n$-bit strings, then it is still vanishing (at an exponential rate), since $2^{n/2}/2^n=2^{-n/2}$.It is not hard to (artificially) construct NP-complete problems  that are  P-density-close, according to the above definition. For example, let $L$ be any NP-complete language, and define $L^2=\{xx\,|\, x\in L\}$. Then $L^2$ retains NP-completeness, but has at most $2^{n/2}$ $n$-bit yes-instances. Therefore, the trivial algorithm that answers no to every input, will correctly decide $L^2$ on almost all inputs; it will err only on a $\leq 1-2^{-n/2}$ fraction of $n$-bit inputs.On the other hand, it would be very surprising if  all NP-complete problems are P-density-close. It would mean that, in a sense,  all NP-complete problems are almost easy. This motivates the question:Assuming P$\neq$NP, which are some  natural NP-complete problems that are not P-density-close? 
Almost easy NP-complete problems
cc.complexity theory;ds.algorithms;complexity classes;np complete