Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
1  
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
1  
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
1  
Parameterized Computational Complexity studies similar problems. –  Kaveh Jul 6 '13 at 19:37

1 Answer 1

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.