Problem to a solution Consider an  NP hard problem $\frak P$ which takes an input of length n 
$\frak P$ can be solved partially by  a factor $ p_i = p(n,i)\in$ [0,1)... by a polynomial time algorithm $\mathcal A(i)$ having time complexity $T_i$(n) $\in [1,\infty)$. 
 Let it be that with successive  increase in  time complexity the fraction of $\frak P$   solved ie $p_i$ improves ( though it can never be 1 through a polynomial time algorithm) ie $T_i(n)> T_j(n)\rightarrow P_i >P_j $
and for a particular $A(i)$ ,$p_i$ may even have a non zero limit as n$\rightarrow\infty$.
 ie  $\lim_{n\rightarrow \infty} p_i=p(n,i)= b_i \in \mathbb R^+$ 

 My question is ...

Q Do we have an example for such a problem $\frak P$ ?

 A: You haven't said precisely what you mean by a partial solution. Let me try to convince you that it actually matters to be precise about this.  The reason is that reasonable-seeming definitions make the issue trivial. 
Theorem. The following are equivalent for any decision problem $A$. 


*

*$A$ admits polynomial-time partial solutions, in the sense that there are polynomial-time algorithms $p_k$, where the function $k\mapsto p_k$ is linear-time computable, where $p_k$ accepts only elements of $A$, and such that $s\in A$ if and only if $s$ is accepted by all sufficiently large $p_k$.

*$A$ admits constant-time partial solutions, in the sense that there are constant-time algorithms $q_k$, where $k\mapsto q_k$ is linear-time computable, where $q_k$ accepts only elements of $A$, and such that $s\in A$ if and only if $s$ is accepted by all sufficiently large $q_k$. 

*$A$ is computably enumerable.
Proof. Clearly $2$ implies $1$, since constant time is polynomial time. And $1$ implies $3$, since on input $s$, we run $p_k$ on $s$ for larger and larger $k$ until we find an accepting instance. If such a $k$ is found, then we accept $s$, showing that $A$ is c.e. Lastly, for $3$ implies $2$, suppose that $A$ is c.e. So there is an algorithm $p$ that accepts $s$ if and only if $s\in A$. Let $q_k$ be the algorithm that on input $s$, runs $p$ for exactly $k$ steps, and accepts if $p$ accepts by that time, and otherwise rejects. So $q_k$ is a constant-time algorithm, taking exactly $k$ steps on any input; the map $k\mapsto q_k$ is linear-time computable; $q_k$ accepts only objects in $A$; and $s\in A$ if and only if $q_k$ accepts $s$ for all sufficiently large $k$, since this will happen once $k$ is above the run time of $p$ on $s$. QED
Since the c.e. sets include many instances of problems well beyond NP, including many undecidable problems, such as the halting problem, I take this theorem to show that there is a need to be precise in what one means by a partial solution. 
