Questions tagged [np-complete]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
2 votes
0 answers

Is OCN=DOCN decidable?

One-Counter Nets (OCNs) are finite-state machines equipped with an integer counter that cannot decrease below zero and cannot be explicitly tested for zero. An OCN $A$ over alphabet $\sum$ accepts a ...
S. M.'s user avatar
  • 21
4 votes
2 answers

A sum with a product-penalty

Let us consider the following optimization-problem: For a given set of tuples $T=(a_1,b_1),\dots,(a_n,b_n)$ and integers $k,C$. The task is to \begin{align} \max \quad & \sum_{i=1}^n x_i \cdot a_i ...
xtyner's user avatar
  • 41
7 votes
1 answer

BIP for Sudoku naturally integral?

I was reading through the following notes regarding solving a 9x9 Sudoku via a binary integer program The formulation is straightforward ...
Ram's user avatar
  • 137
1 vote
1 answer

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 ...
prakash gawas's user avatar
2 votes
1 answer

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 ...
prakash gawas's user avatar
4 votes
0 answers

bilinear problem proof for NP-completeness of degeneracy check

In the paper "Some NP-complete problems in linear programming" (, there are several proofs given to show that testing for degeneracy in LPs is NP-...
Brannon's user avatar
  • 892