Questions tagged [np-hardness]

Questions related to NP-hardness and NP-completeness.

Filter by
Sorted by
Tagged with
0 votes
0 answers
39 views

Are the Eigendecomposition and Singular Value Decompositions in the class P?

I can run, for instance, np.linalg.eig or np.linalg.svd on my computer in polynomial time. However, my understanding is that if the intermediate steps require too many bits to express and give NaNs or ...
user avatar
1 vote
1 answer
69 views

Exact Cover by 3-Sets variation: Partition Into Exact Covers by 3-Sets

In the Exact Cover by 3-Sets problem, we are given a set $X = \{x_1, x_2,\ldots, x_{3n}\}$ and a family of subsets $F = \{\{x_{i_1}, x_{i_2}, x_{i_3}\}\}$ of 3-element subsets of $X$. The question is ...
user avatar
  • 11
1 vote
1 answer
144 views

Hardness of a class of quadratics

I have a system of inequalities of the form $x_i^2 \le x_j$ with $x_i = a_i + \sum_j \alpha_j b_{i,j}$, the variables are $x_i,\alpha_i$, the values $a_i, b_{i,j} \ge 0$ are known and all $x_i, a_i, \...
user avatar
0 votes
1 answer
79 views

Is "choosability of subsets" NP-hard?

Let $n\in\mathbb{N}$ be a positive integer, and let ${\cal A}$ be a collection of subsets of $n=\{0,\ldots,n-1\}$. We say ${\cal A}$ has the choosability property if there is $R\subseteq n$ such that $...
user avatar
0 votes
0 answers
131 views

Relation between BSS and Turing models

$P_\mathbb R$ is the set of languages decidable in polynomial time over the real $BSS$ machine defined in https://en.wikipedia.org/wiki/Blum%E2%80%93Shub%E2%80%93Smale_machine. Let $0-1-P_\mathbb R=\{...
user avatar
  • 12.5k
0 votes
1 answer
124 views

The Complexity of Multi-Objective Optimization

Given a vector set $V=\{v_i\}_{i=1}^n$ with $n$ vectors where $v_i\in \mathbb{R}^d$ is a vector and a transfer matrix $\mathbf{W}\in \mathbb{R}^{d_1\times d}$, the target is to select two subsets $V_1=...
user avatar
  • 57
0 votes
0 answers
86 views

Complexity of the distance between the average vector of two subsets

Given a vector set $V=\{v_i\}_{i=1}^n$ with $n$ vectors, where $v_i\in \mathbb{R}^d$ is a vector, the target is to select two subsets $V_1=\{v_j\}_{j=1}^{|V_1|} \subset V$ and $V_2=\{v_k\}_{k=1}^{|V_2|...
user avatar
  • 57
2 votes
1 answer
170 views

Complexity of the Complete (3,2) SAT problem?

A complete $k$-CNF formula is a $k$-CNF formula which contains all clauses of size $k$ or lower it implies. Deciding the satisfiability of a complete $k$-CNF formula is clearly a tractable problem ...
user avatar
2 votes
0 answers
135 views

Which hypergraphs can be simplified by alternatively removing a hyperedge and an isolated vertex?

Let $H = (V, E)$ be a hypergraph, with $V$ the set of vertices and $E \subseteq 2^V$ the set of hyperedges. An elimination sequence on $H$ consists of alternatively removing hyperedges. Specifically, ...
user avatar
  • 7,455
0 votes
0 answers
80 views

What are the capabilities of current Boolean Satisfiability Solvers?

I am wondering how well current Boolean Satisfiability solvers are able to perform — for example, are the best SATsolvers able to solve problems from SATlib?
user avatar
2 votes
0 answers
68 views

Prize Box Ordering Problem With Position Constraints: Easy or Hard

I have a problem where we have $n$ boxes, each box $i$ have probability $p_i$ of containing a prize with value $h_i > 0$, and remaining probability of containing nothing. Now we are asked to order ...
user avatar
2 votes
1 answer
142 views

Is the weighted sum of subset prefix product problem NP-hard?

I have this strange problem where we have a set of positive numbers $M$, a fixed number $n$, and a function $f: M \rightarrow R^+$ mapping each number in M to another positive number. We want to know ...
user avatar
2 votes
0 answers
118 views

SUBSET SUM "with error"

Has a SUBSET-SUM "with error" variant been studied - and with error, I mean, instead of a single target value $k$, a target interval $[k-\varepsilon,k+\varepsilon]$ ($\varepsilon>0$ very ...
user avatar
  • 199
5 votes
0 answers
106 views

Joint Scheduling Problem with Variables Arrival Times

The scheduling problem $1\bigl|r_j\bigl|\Sigma\,U_j$ is strongly NP-hard but when preemption is allowed the scheduling problem $1\bigl|pmtn,r_j\bigl|\Sigma\,U_j$ becomes strongly polynomial. I have a ...
user avatar
  • 325
2 votes
1 answer
236 views

The complexity of 3SAT

It is well known that 3SAT remains NP-complete if every variable occurs exactly twice positively, exactly once negated. then, does 3SAT remain NP-complete if every variable occurs exactly once ...
user avatar
1 vote
0 answers
111 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-...
user avatar
2 votes
0 answers
41 views

Is the following special case of multiway number partitioning NP-hard?

The following problem is a decision problem of multiway number partitioning (wikipedia) (Note that $k$ is also a part of an input in the following problem, while $k$ is a fixed number in wikipedia ...
user avatar
0 votes
0 answers
101 views

What type of Problems (Class and types) Can Be Solved Effectively with Quantum Computers?

The Question: I'm trying to understand the type of problems that Quantum Computers are/will be good at solving and if there is a special class to categorizes these types of problems (e.g. Do we ...
user avatar
1 vote
1 answer
180 views

How to show that Color Tiles is NP-Complete

Color Tiles is a puzzle game where color tiles are laid out in a rectangular grid. A tile is visible to an empty grid cells if there is a clear line-of-sight in one of the 4 cardinal directions (You ...
user avatar
1 vote
1 answer
69 views

Set cover with rewards

I am dealing with the following problem: Given a universe $U$, let $\mathcal{S}$ be a family of subsets of $U$. Each subset $S\in\mathcal{S}$ is associated with a non-negative reward, and each element ...
user avatar
2 votes
0 answers
82 views

NP-hardness of Euclidean k-Median for k = 2

In the Euclidean $k$-median problem, we are given a set $C$ of clients in $\mathbb{R}^d$. The task is to open a set $F \subset \mathbb{R}^d$ of $k$ facilities such that the cost function $\Phi(F) = \...
user avatar
4 votes
0 answers
92 views

Analogue of Chow-Liu tree for $L_1$

Say $\Omega$ is a finite set and $f$ a probability mass function (pmf) over $\Omega^d$. Now let $T$ be a spanning tree on the set $V=\{1,2,\ldots,d\}$, and consider a collection of one- and two- ...
user avatar
  • 10k
1 vote
1 answer
113 views

Hardness of computing the dimension of an integral polytope?

Given a set of linear inequalities $Ax \leq b$ let $P = \text{conv}\{x \in \{0,1\}^n \mid A x \leq b \}$ be the convex hull of all binary vectors that satisfy the given inequalities. I am interested ...
user avatar
  • 25
1 vote
0 answers
76 views

A reduction from the maximum $k$-closure problem to the clique problem

Fix a partially ordered set $(P, \le)$ with $N$ elements and real weights $w(p)$ for each $p \in P$. A subset $S \subset P$ is called closed if for any $x, y$ with $y \in S$ and $x \le y$ we also ...
user avatar
  • 111
0 votes
0 answers
73 views

Subset Sum Problem exact Algorithm (hypothetical)

Let assume there is way to apply a divide & conquer approach to the classical subset sum solver of Horowitz and Sahni. And for this, we design a decomposition function, when applied to the ...
user avatar
0 votes
0 answers
37 views

Bounded-Frequency Minimum Set Cover Problem

Consider the special case of the minimum set cover problem where each element of the universe occurs in at most 3 sets. Can this problem be solved in polynomial time? Is there a nontrivial upper ...
user avatar
  • 101
1 vote
1 answer
55 views

Maximize the absolute value of connected nodes after $k$ modifications

Given a graph $G=\{V,E\}$, each node $i$ has a value $v_i$. Given budget $k$, we have $k$ chance to add 1 or minus 1 for a node's value, for example, $v'_i=v_i+1$ or $v'_i=v_i-1$. In particular, $v'_i$...
user avatar
  • 57
2 votes
1 answer
105 views

Can this special case of Node Weighted Steiner Tree be solved in polynomial time?

Consider the node-weighted steiner problem: Input: a graph $G=(V,E)$, a set $T\subseteq V$ of terminals, a weight function $w: V\setminus T \to \mathbb{R}_+$. Output: a minimum weight subset $S \...
user avatar
1 vote
1 answer
208 views

Can this NP-hardness proof for Super Mario Brothers (and other games) be simplified?

In "Classic Nintendo Games are (Computationally) Hard", a generalized framework based on reducibility of 3-SAT for proving NP-hardness of classic Nintendo games is presented, and several ...
user avatar
  • 11
2 votes
2 answers
136 views

Status of certain problems in knot theory

I found it somewhat difficult to understand the status of certain problems from knot theory. Is it correct to say that it's been neither proved nor disproved that any of the following problems are NP-...
user avatar
-1 votes
1 answer
88 views

Is finding the shortest consistent term to fill a missing line in a truth table still NP-hard?

I understand the logic minimization problem is NP-hard when given the onset, since the last step is equivalent to set cover optimization. If instead we are given a partial truth table, and we just ...
user avatar
  • 203
1 vote
1 answer
144 views

Is QMA known to contain Co-NP?

Is QMA known to contain Co-NP? If not, would Co-NP being contained in QMA have any implications for other complexity classes. (e.g. Causing the polynomial heirachy to collapse.)
user avatar
0 votes
1 answer
184 views

Lexicographic Boolean satisfiability

Maximal Satisfying Assignment (Lexicographic Boolean satisfiability / LexMaxSAT), the problem of finding the lexicographically maximum x_1, . . . , x_n ∈ {0, 1}^n that satisfies Boolean formula φ, or ...
user avatar
0 votes
0 answers
50 views

Is p-dimensional matching with (p−1)n edges NP-hard? What about 3n edges?

Let $p≥3$ an integer. I am wondering whether or not the following problems are NP-hard or not (and if they are, I am looking for a convincing argument, or even better a detailed proof): Let $V_1,\...
user avatar
4 votes
0 answers
132 views

An NP-hard Hidden Subgroup Problem

I've encountered a model which can be thought of as a version of the Hidden Subgroup Problem (https://en.wikipedia.org/wiki/Hidden_subgroup_problem), but that doesn't quite meet the standard problem's ...
user avatar
  • 5,261
2 votes
1 answer
160 views

Coloring intersection graph of squares

It is known that the coloring intersection graph of axis-parallel rectangles is NP-Hard. What about squares and more specific case "unit squares"? Thanks.
user avatar
  • 21
1 vote
0 answers
41 views

Modifying sets to minimize the distance among each pair of the mean value of sets

Given $n$ points, each point $x_i$ has a value $v_i \in \mathbb{R}^{d}$, and there are $m$ point sets $\{S_1,\dots, S_m\}$ that each point set consists of some points. The size of point sets can be ...
user avatar
  • 57
7 votes
1 answer
287 views

Hardness of maximizing $x^TAy$ with $\{-1,1\}$ entries

My question concerns the NP-hardness of the following discrete optimization problem: Given a matrix $A \in \{ \pm 1 \}^{m\times n}$, $$\begin{array}{ll} \underset{x \in \{ \pm 1 \}^m ,\, y \in \{ \pm ...
user avatar
  • 73
-2 votes
1 answer
69 views

Is time-slot matchmaking NP-hard?

I have the following problem, which I intuitively expect to be NP-hard but cannot see how to write a reduction for: Givens: There is a fixed set of time slots, e.g. {9-10, 10-11, 11-12, 12-1, etc.}. ...
user avatar
5 votes
1 answer
237 views

$\rho OPT + k$ approximation for bin packing (Unpublished result of David P. Williamson)

I am currently stuck on Exercise 5.12 in this book, which is apparently an unpublished result of David P. Williamson according to the book notes. The problem asks to use randomized rounding and first ...
user avatar
1 vote
0 answers
152 views

Triangle detection hardness in regular graphs

Consider a tripartite graph over $n^{1-\epsilon}$ vertices each in sets $I, J, K$. Suppose we impose a constraint that every vertex has degree $n^\epsilon/c$ for some constant $\epsilon > 0$ and ...
user avatar
  • 1,015
3 votes
0 answers
141 views

Computational complexity of minimum distance of rate $\frac{1}{2}$ codes

We know from Berlekamp, McEliece and Van Tilborg [On the inherent intractability of certain coding problems, IEEE Trans. Information Theory, 24 (1978)] that computing minimum distance of a (binary) ...
user avatar
  • 387
3 votes
1 answer
348 views

How hard is this combinatorial optimisation problem?

Suppose we have multiple intervals $R_1,R_2,...,R_i$ of non-negative integers. These intervals may overlap and we use $R_h(\mathrm{median})$ to denote the median integer in the $h$-th interval $R_h$, ...
user avatar
8 votes
1 answer
180 views

Finding vertex separator such that the induced subgraph has minimal number of edges

My problem is related to edge and vertex cuts with a little twist. Given a graph $G$ and two vertexes $u$ and $v$. I want to find a set of vertexes $S \subset V$ that disconnects $u$ and $v$ such that ...
user avatar
  • 183
2 votes
1 answer
74 views

Covering a binary relation as a union of rectangles

Given finite sets $X$ and $Y$ and a subset $R\subset X\times Y$, I want to express $R$ as a union $R=\bigcup_{i=1}^n X_i\times Y_i$ with $n$ as small as possible. Here, each $X_i\subset X$ and $Y_i\...
user avatar
2 votes
2 answers
369 views

Proving not NP-complete by non-existence of gadget

Suppose we suspect a problem to be polynomial time solvable, but we are unable to prove this. So, we attempt to prove that the problem cannot be NP-hard. Known proofs in this direction show that if ...
user avatar
4 votes
1 answer
230 views

Complexity of relaxed edge colouring

A (proper) $k$-edge colouring of a graph $G(V,E)$ is a function $f:E\to\{1,2,\dots,k\}$ such that adjacent vertices are mapped to different colours; that is, $f(e)\neq f(e')$ if $e$ and $e'$ are ...
user avatar
1 vote
0 answers
86 views

Is there a "common" name for this type of combinatorial optimization problem?

I'm trying to find papers that discuss approaches (in particular, any Deep Learning or Deep Reinforcement Learning techniques) that could be used used to solve the problem described in the next ...
user avatar
4 votes
0 answers
91 views

Inverting Kronecker product on vectors is in P?

Problem: Given a vector V of positive integers, find two vectors v1 and v2 such that the Kronecker product of v1 and v2 is equal to p(V) (where p(V) is a suitable permutation of V). Example: Input: V={...
user avatar
  • 61
1 vote
2 answers
216 views

Two valued variant of subset sum problem

I'm interested in the complexity of the following problem: Given a multiset $S$ containing only two positive integers $a$ and $b$, find a $k$-partition of $S$ that maximizes the sum of part with ...
user avatar

1
2 3 4 5
14