# Questions tagged [np-complete]

The tag has no usage guidance.

6 questions
Filter by
Sorted by
Tagged with
121 views

### 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 ...
• 21
111 views

### 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 ...
• 41
294 views

### BIP for Sudoku naturally integral?

I was reading through the following notes regarding solving a 9x9 Sudoku via a binary integer program https://vanderbei.princeton.edu/tex/talks/INFORMS_19/Sudoku.pdf The formulation is straightforward ...
• 137
1 vote
85 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 ...