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$. 

 1. $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$.

 2. $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$. 

 3. $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 exactly the $s$ that are in $A$. Let $q_k$ be the algorithm that on input $s$, runs $p$ for exactly $k$ steps, and accepts if $p$ accepts, and otherwise rejects. So 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

I take this theorem to show that there is a need to be precise in what one means by partial solution.