We study the class of P-Complete problems and show the following: i) for any constant e ≫0 there is a P-complete problem for which an e-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.
['Sartaj Sahni', 'Teofilo Gonzales']
P-complete problems and approximate solutions