---

1996 Volume

---

Date: Fri, 05 Sep 1997 22:21:34 -0600
From: aaron_zhang@hotmail.com
Subject: NP-hard?
Could anyone expain me what the exact meaning of NP-hard? Thanks in advance.

Aaron

Date: Fri, 21 Feb 1997 17:12:33 +0100
From: Michael Schroeder <schroeder@andor.wiwi.uni-karlsruhe.de>
Subject: computational complexity question
Look at the following "weak subset sum" problem:

Given are n positive integers a_1,...,a_n and bounds L and U with a_i < L for all i and U - L > (max a_i)/(C*n^k). In the latter C > 0 and k >= 0 are _fixed_.

It is to decide whether there is a subset I of 1,...,n with L <= sum (a_i : i in I) <= U.

My question: Is this problem NP-hard? Any hints or references are welcome.

Remark 1:
Please note that the answer would be easy if the "gap" U - L weren't bounded from below in the above manner, since then the problem would include the subset sum problem which is well known to be NP-hard.

Remark 2:
The problem can be regarded as a subset sum problem in which only the t most significant bits of the right hand side are prescribed, with t bounded by a polynomial in log n. The variant of the problem in which only the t _least_ significant bits are prescribed is clearly polynomially solvable by doing additions modulo 2^t. The key in our problem is that we can't ignore what happens in the lower bits, since carries are possible when adding.

Remark 3:
Let integers b_i,c_i defined by a_i = b_i*(U - L) + c_i with 0 <= c_i < U - L. I have a method which runs in time not worse than O(n^r) where r = cardinality of the set of all b_i. Consequently it is polynomially if k=0 and C>0 fixed and answers my question for this case. (Unfortunately it is too long to state it here.) So I'm mainly interested in the situation with k>0.

Date: Thu, 16 Jan 1997 13:46:54 -0100
From: Fabio Schoen <schoen@ingfi1.ing.unifi.it>
Subject: Complexity of norm maximization
If we want to maximize the norm of a vector x subject to linear constraints, we generally obtain an NP-hard problems (very few exceptions like, e.g., 2-norm on a hypercube).

Is there any known result on special polyedra like, e.g., a "parallelotope" (a lineare trasformation of the hypercube into a polyedron whose faces are pairwise parallel)?

Date: 21 Dec 1996 00:29:11 GMT
From: naylor@synopsys.com (William Naylor)
Subject: NP-complete kludge?
If P != NP then it is impossible to write a program that solves all NPC problem instances in polynomial worst case time.

But perhaps a weaker solution than this is still be possible, which would still "solve" NP-complete problems in a practical sense. For example, a program which gives the right answer for "most" NPC problem instances, "usually" in polynomial time. If "most" means 95% of problems, and "usually" means 95% of problems, this solution might be quite useful. And perhaps, you can't prove these properties, but experience tells you that it is so.

Has such a program ever been written? Would people consider it interesting if it could be written?

Date: 21 Dec 1996 18:32:12 -0800
From: nordwick@scam.XCF.Berkeley.EDU (Jason Alan Nordwick)
Subject: NP-complete kludge?

jay

The simplex method has an interesting property, however. In practice, it has been observed to take a polynomial amount of time for nearly every problem. It just has this nasty property that there exists some problem for any simplex method pricing rule that will cause the algorithm to blow up exponentially.

Now let me move from fact to opinion. NP-complete problems all belong to the same complexity class in the theoretical sense. However, I believe that some NPC problems are *much* easier than others. For example, I think that the knapsack problem is one of the easiest NPC problems because we have a fast pseudopolynomial algorithm: dynamic programming. Moreover, we can find many instances of knapsack problems that *can* be solved in polynomial time: when all objective coefficients (or constraint coefficients) are equal.

OTOH, I believe that integer programming is one of the "hardest" NPC problems in practice since most NPC problems may be represented by an integer program.

Mike hennebry@plains.NoDak.edu
There are three kinds of people, those who can count and those who can't.

-- I. Forget

Crawl back to front page.