# 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$ ?

-
I think that if you formally define what a "partial solution" is and what "the fraction of $P$ solved by $p_i$" means, it will be easy to find examples. –  Goldstern Jul 6 '13 at 13:35
Well ...$\frak P$ can be the graph coloring problem, number of edges will be n, Percentage of edges having different colors at ends ( colored by $\mathcal A_i$) will be $p_i$ –  awa Jul 6 '13 at 13:50
...just that approximation algorithms for NP hard problems have not been treated as a continuum. cs.cmu.edu/afs/cs/academic/class/15750-s01/www/notes/lect0320 –  awa Jul 6 '13 at 13:54
Are you familiar with polynomial-time approximation schemes (en.wikipedia.org/wiki/Polynomial-time_approximation_scheme)? They seem to fit your definitions to me (i.e. let $i = 1 - \epsilon$). –  usul Jul 6 '13 at 14:32
Parameterized Computational Complexity studies similar problems. –  Kaveh Jul 6 '13 at 19:37

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

-