What work has been done on approximation schemes for $\mathsf{P}$-complete optimization problems? Would the desired approximation algorithms here be "fully log-space approximation schemes" or "fully $\mathsf{NC}$ approximation schemes", analogous to $\mathsf{FPTAS}$ for $\mathsf{NP}$ optimization problems?

  • 2
    $\begingroup$ Why is P-completeness a relevant notion for approximations ? Are you limited to logspace in some way ? and why ? $\endgroup$ Jan 30, 2012 at 21:26
  • 4
    $\begingroup$ You might be interested in this paper: Till Tantau, Logspace Optimization Problems and Their Approximability Properties, Theory of Computing Systems 41(2), pp. 327-350 (2007), springerlink.com/content/m52274505l5344g6 $\endgroup$ Jan 31, 2012 at 8:50
  • 3
    $\begingroup$ Try searching NCAS and FNCAS. $\endgroup$ Jan 31, 2012 at 14:31

1 Answer 1


This one seems related, although it focuses more on parallel time (NC) rather than the closely related space (L): http://www.springerlink.com/content/8hn2q8lvf3ukbbx0/


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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