  We introduce a concept of efficiency for which we can prove that it applies
to all paddable languages, but still does not conflict with potential worst
case intractability. Note that the family of paddable languages apparently
includes all known natural NP-complete problems. We call our concept Roughly
Polynomial Time (RoughP). A language $L,$ over an at least 2-symbol alphabet,
is in RoughP, if the following hold: (1) there exists a bijective encoding
$\alpha$ of strings, such that both $\alpha$ and its inverse are computable in
polynomial time; (2) there is a polynomial time algorithm $\cal A$, which is an
errorless heuristic for $L,$ with exponentially vanishing failure rate relative
to the $\alpha$-spheres $S^{(\alpha)}_n=\{\alpha(x)\,|\;\, |x|=n\}$. It means,
$\cal A$ always correctly decides whether $x\in L$ or $x\notin L$, whenever it
outputs a decision. For some inputs, however, it may not output a decision,
rather it may return a special sign, meaning "don't know." But the latter can
happen only on an exponentially small fraction of each $\alpha$-sphere. We
prove that RoughP contains all paddable languages. This may contribute to the
explanation of the often observed gap between practical algorithm performance
and theoretical worst case analysis for hard problems. Furthermore, the proof
also provides a general method to construct the desired encoding and the
errorless heuristic. Additionally, we also show how to use it for efficiently
generating large, random, guaranteed positive and negative test instances for
any paddable language, including all known natural NP-complete problems. In
fact, it appears that every practical decision task (whether in NP or not) can
be represented by paddable languages, and, therefore, our RoughP framework
applies to all of them. We also explore some connections between RoughP and
other complexity classes.
