出现在优化逼近中的核

很多组合优化问题不太可能存在多项式时间的算法,人们往往利用多项式时间的近似算法去逼近这一问题的精确解。但有时也会出现这样的情况:对于某个优化问题,在逼近误差不超过某个函数f的限制下仍然不存在多项式时间的近似算法。对于这样的问题A,本文将证明存在两个包含无穷元素的核A_1,A_2,它们满足:(1)若h是问题A多项式时间的近似算法,则对于A_1中的所有元素(有限个例外),h的误差都大于f;(2)若h是问题A的近似算法,而且逼近误差不超过f,那么对A_2中的几乎所有元素(有限个可能例外)。