Questions tagged [np-hardness]
Questions related to NP-hardness and NP-completeness.
691
questions
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$,...
- 135
-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 ...
- 21
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 ...
- 3,246
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 ...
- 153
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 ...
- 71
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 ...
- 3,246
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 ...
- 475
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 ...
- 10.8k
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?
- 79
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 ...
- 11
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$ ...
- 1,859
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)$...
- 597
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.
...
- 1,859
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, \...
- 889
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 ...
- 1,069
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?
- 1
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 ...
- 43
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 ...
- 43
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 ...
- 79
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 ...
- 21
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 ...
- 109