Question

线性规划问题是一个np-hard问题对吗

Answer 1

线性规划不是NP难，它可以用单纯型（simplex）法求解。线性整数规划是NP难问题，但也有一般解法，比如cut plane法，分支界定法。其他NP难问题无一般解法，需要heuristic方法求解。

Answer 2

NP完全(NP Complete,NPC)问题是指这样一类NP问题，所有的NP问题都可以用多项式时间划归到他们中的一个。所以显然NP完全的问题具有如下性质：它可以在多项式时间内求解，当且仅当所有的其他的NP－完全问题也可以在多项式时间内求解。
NP完全问题，是世界七大数学难题之一。 NP的英文全称是Non-deterministic Polynomial的问题，即多项式复杂程度的非确定性问题。简单的写法是 NP=P？，问题就在这个问号上，到底是NP等于P，还是NP不等于P。
NP-hard，其中，NP是指非确定性多项式（non-deterministic polynomial，缩写NP）。所谓的非确定性是指，可用一定数量的运算去解决多项式时间内可解决的问题。