MAX SAT AND MIN SET COVER APPROXIMATION ALGORITHMS ARE $\mathcal P$-COMPLETE
Giancarlo Bongiovanni, Pierluigi Crescenzi, Sergio De Agostino · Parallel Processing Letters · 1995
We prove that the sequential approximation algorithms for the problems [Formula: see text] and [Formula: see text] proposed in [9] are [Formula: see text]-hard with respect to the logarithmic space reducibility. As a corollary, these two algorithms cannot be implemented efficiently in parallel unless [Formula: see text].