The 2024 Developer Survey results are live! See the results

# Questions tagged [np-hardness]

Questions related to NP-hardness and NP-completeness.

745 questions
Filter by
Sorted by
Tagged with
33 views

### On generating tight instances of Max Cover / NP-hard Problems

In the Max Cover NP-hard problem, a greedy algorithm provides a theoretical lower bound of $(1-1/e) \cdot OPT$, where OPT represents the optimal solution (reference). I am interested in randomly ...
149 views

### Complexity of 2-coloring with extra constraints

I am considering the following problem: Given a graph $G=(V,E)$ with $|V|=4n$ vertices, can we color the vertices in two colors (red and blue) with The usual constraint that two vertices connected by ...
80 views

136 views

### Shortest path with affine updates and fixed dimension

One may look at the shortest path problem on a weighted directed graph with weights on $\mathbb{Q}$ as the problem of minimizing a rational value $x$ which is updated at each edge of the graph with ...
5k views

201 views

### What’s the complexity of this decision problem with bit shifting?

I’ve been wondering about the computational complexity of a problem that involves bit shifting. Let me define some notation before I present the problem. If $\langle{b}\rangle$ is a bitstring ...
31 views

### Hardness of 3-Partition with Small Target Value

In the 3-partition problem, we are given a set of positive integers $a_1,\ldots,a_n$ and a target value $T$; the goal is to decide if there is a partition of the numbers to triplets such that the sum ...
178 views

### Is counting the union of power sets NP-complete?

Say we have $n$ sets $A_1,\dots,A_n$ with elements from a universal set $U$. We want to compute the cardinality of $\cup_{i=1}^n 2^{A_i}$ or at least decide on non-trivial bounds. Is this problem NP-...
74 views

### The hardness of active learning with fixed budget

I have been looking for theoretical papers studying this question of the hardness of PAC active learning algorithms. I found a few papers studying the problem from a fixed perspective (particular ...
52 views

### Is this variant of Facilities location problem a NP-hard problem?

Given a set of locations $P=\{p_1,p_2,\dots\}$ and a set of facilities $F=\{f_1,f_2,\dots\}，|F|\ge k$ on a plane. We want to partition the facilities into $k$ disjoint subsets (each subset has at ...