Talk:APX

APX-complete, APX-hard[edit]

This description introduces the word 'complete' in the APX context without explaining it, then launches into a new paragraph that opens with APX-hard, then refers to the unexplained APX-complete to contrast APX-hard in an extremely difficult-to-follow fashion. Please somebody who has a clue what this is about, explain APX complete and then make the way APX-complete is used to explain APX-hard clearer. 71.141.225.199 16:25, 19 January 2007 (UTC)[reply]

I guess I just assumed that anyone studying an advanced topic in complexity theory would already be familiar with completeness and hardness. I can expand on this. Deco 16:58, 19 January 2007 (UTC)[reply]

I've explained in more detail the definitions of APX-hard, APX-complete, and written an article on PTAS reductions. Hope this helps. Deco 00:04, 20 January 2007 (UTC)[reply]

Max SNP[edit]

(How) Does APX relate to Papadimitriou and Yannakakis's "Max SNP"? I couldn't find an entry for Max SNP and thought this might mention it. Thanks LachlanA 21:52, 11 September 2007 (UTC)[reply]

Great question. See this blog entry for answers. I'll leave the question of how to incorporate this into Wikipedia up to future consideration. Dcoetzee 22:22, 14 September 2007 (UTC)[reply]

Inapproximable problems[edit]

Are there problems in NPO which do not belong in APX?

If P=NP, is APX=NPO? 217.132.179.156 (talk) 21:26, 26 October 2008 (UTC)[reply]