Questions tagged [np-complete]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
1 vote
1 answer
47 views

complexity Partitioning with negative numbers

I want to partition a set of numbers in two sets such that their sum is equal. Here in the original master set we can have positive as well as negative numbers. Can anyone tell me about the complexity ...
2 votes
1 answer
105 views

Np-hard sequencing or packing problems with total ordering between elements

I would like to know if anyone is aware of any Np-hard problems in scheduling or packing where there is total ordering between tasks or items to be packed together. The objective can be anything. For ...
4 votes
0 answers
49 views

bilinear problem proof for NP-completeness of degeneracy check

In the paper "Some NP-complete problems in linear programming" (https://doi.org/10.1016/0167-6377(82)90006-2), there are several proofs given to show that testing for degeneracy in LPs is NP-...