# Approximation schemes for P-complete problems?

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?

• Why is P-completeness a relevant notion for approximations ? Are you limited to logspace in some way ? and why ? – Suresh Venkat Jan 30 '12 at 21:26
• 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 – Jan Johannsen Jan 31 '12 at 8:50
• Try searching NCAS and FNCAS. – Tsuyoshi Ito Jan 31 '12 at 14:31