Questions tagged [np-hardness]

Questions related to NP-hardness and NP-completeness.

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

$NP \subseteq PSPACE$ proof clarification on enumeration of all solutions [closed]

I was asked to prove that NP is a subset of PSPACE using certificates (no reductions). It's incredibly obvious if you can iterate through every possible solutions of the problem in polynomial space, ...
  • 109
0 votes
0 answers
32 views

Reduction of Monotone-1-in-3-SAT to Cubic-Monotone-1-in-3-SAT

3-SAT is an NP-Complete problem. Now given a 3-SAT instance it can be transformed to a Monotone-1-in-3 SAT instance thus even Monotone-1-in-3-SAT is NP-Complete (am aware of this reduction). But, as I ...
  • 304
2 votes
1 answer
49 views

Balls in monochromatic bins

Suppose we have a collection of $m$ balls in $k$ different colors. Let $b_i$ be the number of balls with color $i$, so $\sum_{i=1}^k b_i = m$. Assume we have $n$ bins with capacities $c_1, \dots, c_n$,...
  • 23
6 votes
0 answers
69 views

Cycle packing with degree condition

Given a directed graph where each vertex has the same in-degree as out-degree, I would like to find the maximum number of edge-disjoint cycles. Is this NP-hard? Without the degree condition, the ...
  • 113
9 votes
1 answer
374 views

Is it NP-hard to find an order on a set of strings so that the concatenation is a given string?

Consider the following decision problem over a fixed alphabet $\Sigma$: Input: strings $s_1, \ldots, s_n$ of $\Sigma^*$ and a target string $t \in \Sigma^*$ Output: does there exist a permutation $\...
  • 8,223
0 votes
1 answer
54 views

Complexity of Exact Cover problem if containing a Set Cover means there is an Exact Cover

As stated in the question, I'm interested in a variant of Exact Cover that is currently relevant to my research. Specifically, a variant where you are promised that if there is a Set Cover of size $k$,...
-1 votes
0 answers
42 views

N-Queens complexity categorization

As I am reading through papers regarding the N-Queens problem, I got caught up whether it is classified to be a NP-Hard problem or otherwise. This paper says that the problem is classified as an NP-...
4 votes
2 answers
158 views

NP-hardness: (planar) directed feedback vertex set problem with bounded degree

My question is the directed version of this one. (I know the results and proofs about feedback vertex set in undirected graphs or undirected planar graphs; so I am concern about the directed feedback ...
  • 397
2 votes
1 answer
100 views

NP-complete problems on posets?

I'm in the midst of some doctoral research and trying to figure out a particularly tricky reduction. I think my best shot is to reduce from an NP-complete problem on posets, if one exists. I did some ...
9 votes
0 answers
134 views

Complexity of $(\Delta-1)$-coloring graphs of maximum degree $\Delta$

Suppose we have a graph $G$ with maximum degree $\Delta$. Deciding if $G$ can be colored with $\Delta$ colors is easy: Brooks' theorem says that this is always possible, unless $G$ is a clique or an ...
13 votes
1 answer
312 views

Is this a known problem, and is it NP-complete?

Does the following problem have a name? Is it NP-complete? Given a multiset of $n$ positive integers, $S$, and an positive integer $m$, does there exist an $m \times n$ matrix whose rows are ...
  • 133
8 votes
1 answer
213 views

Is it $NP$-hard to check whether a given algebraic circuit computes permanent?

Given are a natural number $n\in\mathbb{N}$ and a polynomial $P$ in the form of an arithmetic circuit $C$ over $\mathbb{Z}$ (a circuit which only uses $+$ and $\times$ gates and integer constants as ...
2 votes
0 answers
52 views

hardness of partition of permutation into a minimum number of monotone subsequences

Given a permutation P, a monotone subsequence is a subsequence (i.e. the elements do not have to be consecutive in P) that increases or decreases. This leads naturally to the following optimization ...
6 votes
1 answer
107 views

Complexity of induced Steiner Tree problem

Consider the following problem: we are given an undirected graph $G=(V,E)$ and three terminal vertices $t_1,t_2,t_3\in V$. We are asked whether there exists a set of vertices $S\subseteq V$ such that ...
4 votes
1 answer
98 views

Complexity of finding a path visiting all leaves on a tree while respecting a distance bound

I am interested in the complexity of a specific variant of the Hamiltonian path problem where we want to visit all leaves of a tree while respecting a distance bound. Formally, given an (undirected, ...
  • 8,223
0 votes
1 answer
73 views

increasing minimum graph degree by adding edges

My problem: Given a graph $G=(V, E)$ and an integer $\ell$,add a minimum number of edges to $G$ so that in the resulting graph every vertex has degree at least $\ell$. Is there a polynomial-time ...
  • 33
1 vote
2 answers
131 views

Is this subsequence problem NP-hard?

Here is yet another "is X NP-hard?" question. The input of the problem is the following: A sequence of $n$ non-negative real numbers $\alpha_1, \ldots, \alpha_n$. Here $n$ is a positive ...
  • 11
2 votes
0 answers
109 views

Computing real numbers with Turing Machines

Consider the following decision problem: Given a two integers $n$ and $k$, decide whether $k=\lfloor n\pi\rfloor$ Question: Is this problem known to be in $P$? Although this may look like a stupid ...
4 votes
1 answer
175 views

Finding a "typical" path

Consider an undirected graph with two distinguished nodes $u\neq v$. How hard is it to find an $u-v$ path, such that its length is as close to the average $u-v$ path length as possible? Formally, for ...
7 votes
1 answer
164 views

Complexity of Maximizing Hamming Distances Below a Threshold

Problem Statement Is the following problem NP-Complete? Input: A collection $S$ of binary strings, with each string of length $m$. Goal: Compute a binary string $s^*$ of length $m$ that mazimizes the ...
  • 98
2 votes
1 answer
89 views

Polynomial time solvable in series parallel graph but NP-hard in graph with bounded treewidth

Whether there is a problem to meet the conditions: it is polynomial time solvable in series parallel graphs but NP-hard in graph with bounded treewidth?
0 votes
0 answers
46 views

Existence of W[1]-Hard construction from multiple hard problems

I am a research scholar working on parameterized complexity. Currently, I am exploring ways to prove the hardness of a problem by providing W[1]-Hard constructions. A problem is known to be fixed-...
1 vote
1 answer
63 views

Running time of SAT and other EXPTIME algorithms [closed]

I need to propose an algorithm for a NP-hard problem. I use dynamic programming which leads to a running time $O(2^s\cdot n^2), s\leq n.$ The algorithm aims to finding a path in a graph $G(V, E)$ (in ...
2 votes
0 answers
114 views

Complexity of a sum with a product

Is the following problem NP-complete: Input: A set of tuples $T = \left\{ t_i=(a_i,b_i) | 1\le i\le n \right\}$, an integer $k$ and numbers $C,D\in \mathbb Q_{\ge 0}$. Question: Exists a subset $S\...
  • 31
0 votes
0 answers
79 views

Parameterized intractability for Twin cover

I am currently working on Parameterized algorithms, especially on the complexity of the given problem when parameterized by twin cover as the parameter. I have read the following papers on formulating ...
-1 votes
1 answer
92 views

Parameters: Twin cover and Vertex cover

I am a research scholar, currently working on parameterized algorithms. I am working on a problem and have been exploring various parameters for which the problem remains unsolved. I have read the ...
0 votes
0 answers
72 views

Tractability with respect to multiple parameters

I am working on the decision version of an NP-complete problem. The problem is known to be fixed parameter tractable(FPT) with respect to the solution size $k$ as the parameter. If I consider another ...
6 votes
0 answers
137 views

Computing Sequences with Addition Chains In pseudopolynomial time?

Computing Sequence $a_1, \ldots, a_n$ with addition chains (CSAC) is the problem of finding the shortest sequence $b_1, \ldots, b_m$ with the following properties: $b_1=1$. Every $b_i$ with $i>1$ ...
4 votes
2 answers
326 views

NP-hard problem which is easy on average

I have a feeling like I read somewhere that the Hamiltonian circuit problem is NP-hard, but it is easy on average, or easy for a random instance. However, I cannot find a reference for that, nor an ...
  • 181
1 vote
0 answers
54 views

Find the minimum cost spider joining a root to some leaves

A spider is a tree with at most one vertex of degree greater than 2. This vertex is called the head of the spider. I am interested in the following problem: We are given an undirected graph $G = (V,E)$...
6 votes
1 answer
230 views

Finding a minimal addition chain for a given number

An addition chain for computing a positive integer $n$ is a sequence of natural numbers starting with $1$ and ending with $n$, such that each number in the sequence is the sum of two previous numbers. ...
0 votes
0 answers
57 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 ...
1 vote
1 answer
103 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 ...
  • 11
1 vote
1 answer
160 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, \...
0 votes
1 answer
87 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 $...
1 vote
0 answers
139 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=\{...
  • 12.6k
0 votes
1 answer
169 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=...
  • 57
0 votes
0 answers
90 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|...
  • 57
2 votes
1 answer
199 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 ...
2 votes
0 answers
150 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, ...
  • 8,223
0 votes
0 answers
89 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?
2 votes
0 answers
72 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 ...
2 votes
1 answer
149 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 ...
2 votes
0 answers
119 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 ...
  • 209
5 votes
0 answers
107 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 ...
  • 325
2 votes
1 answer
122 views

Optimal solution for partitioning convex polygon

Given a convex polygon $P$ (possibly) with holes. We want to partition $P$ into a minimum number of connected interior-disjoint polygons $P_1,...P_s$. The definition of restriction on the pieces is ...
  • 133
2 votes
1 answer
279 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 ...
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-...
2 votes
0 answers
66 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 ...
0 votes
0 answers
107 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 ...

1
2 3 4 5
14