We study the class of P-Complete problems and show the following: i) for any constant ε ≫0 there is a P-complete problem for which an ε-approximate solution can be found in linear time ii) there exist P-Complete problems for which linear time approximate solutions that get closer and closer to the optimal (with increasing problem size) can be found iii) there exist P-Complete problems for which the approximation problems are also P-Complete.
No takes yet. Share an insight, caveat, or question.
Sahni et al. (1974) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: