Questions tagged [np-hardness]
Questions related to NP-hardness and NP-completeness.
713
questions
3
votes
1
answer
169
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 ...
2
votes
0
answers
21
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 ...
- 173
0
votes
0
answers
67
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 ...
- 53
2
votes
0
answers
46
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 ...
- 21
6
votes
0
answers
84
views
Certifying the promise in hard promise problems
Do we happen to know of any promise problems where the problem is both conditionally hard (say, NP-hard) while simultaneously being able to certify that the instance satisfies the given promise?
For ...
- 801
0
votes
0
answers
123
views
Could we build PSPACE-based cryptography - more secure post-quantum?
It seems not safe to exclude possibility of e.g. some next generation quantum computers being able to attack NP problems (e.g. 2WQC) - so maybe it is worth to start thinking of shifting the ...
- 325
1
vote
0
answers
84
views
Generalization of the Hamiltonian path problem on Grid Graphs
Fix a cost to each of these actions: move up, move down, move left, move right. I.e. fix some function $f: \{\text{move up, move down, move left, move right}\} \to \mathbb N$.
Define the following ...
- 31
0
votes
1
answer
65
views
Is this edge-partitioning NP-Hard?
Let $G = (V,E)$ be an undirected graph with $m = |E|$ edges (assume that $m = 3t$ for some $t \in \mathbb{N}$).
Problem: Partition $E$ to $q = \frac{m}{3}$ sets $S_1,S_2,\ldots, S_q \subseteq E$ sets ...
- 173
3
votes
0
answers
162
views
Is $\mathsf{NP}\subseteq\mathsf{NSPACE}(n)$?
It is well-known that $\mathsf{P}\neq\mathsf{SPACE}(n)$, either for $\mathsf{SPACE}=\mathsf{DSPACE}$ or $\mathsf{NSPACE}$, and it is conjectured that both $\mathsf{P}\not\subseteq\mathsf{DSPACE}(n)$ ...
- 131
12
votes
1
answer
229
views
Complexity of 1-or-3-in-3-SAT (odd-3-SAT)
Consider a 3-CNF formula $\Phi$, i.e., a conjunction of clauses of 3 literals. I call odd-SAT (or 1-or-3-in-3-SAT) the problem of checking whether there is an assignment of the variables such that ...
- 8,896
0
votes
0
answers
32
views
Hardness of finding minimal subsets that will change the maximum of a univariate polynomial
Given a univariate polynomial of the form $p(x) = \prod_{0 \leq i \leq N}{(x*a_i + b_i)}$ when all of the $a_i$ and $b_i$ are numbers in the range [-1,1] and $i$ goes from $0$ to $N$ (we are given all ...
- 11
1
vote
0
answers
75
views
Hardness of maximization of a univariate polynomial (as a function of its degree)
Given a univariate polynomial of the form $p(x) = \prod_{i}{(x*a_i + b_i)}$ when all of the $a_i$ and $b_i$ are numbers in the range [-1,1] and $i$ goes from $0$ to $N$.
What is the complexity of ...
- 11
0
votes
0
answers
64
views
Enumerating all set covers with sets of size at most two
I am working on enumerating all the set covers (need not be minimal). A branching algorithm runs in $O^*(1.2353^{|U|+|S|})$ time that branches on all the sets of size at least three. As the branching ...
0
votes
0
answers
58
views
Prove that Vertex Cover is NP-Complete by reducing MaxCut to Vertex Cover
This is not the most straight forward reduction available on the internet since most people start from the fact that vertex cover is NP-complete and reduce a given vertex cover instance to MaxCut ...
- 11
1
vote
0
answers
84
views
Complexity of n-rooks completion
I am motivated by the post, Complexity of n-queens-completion. I am interested in completion problem of non-attacking rooks on a chessboard.
Input: Given a chessboard of size $n*n$ with $n-k$ rooks ...
- 20.8k
4
votes
0
answers
129
views
Complexity of numerical 3-dimensional matching where the three multisets are identical
Consider the following problem:
Input: one multiset $S = \{s_1, \ldots, s_n\}$ of positive integers written in unary
Output: can we build $n$ triples that sum to the same value, using each element of ...
- 8,896
2
votes
1
answer
102
views
clique problem in graphs with bounded degree
Is the problem of finding a clique of size $d$ in a graph of maximum degree $d$ NP-complete ($d$ part of the input)?
- 23
3
votes
1
answer
173
views
Which 1-player games are EXPTIME-complete? Also, are there any known games that are EXPSPACE-complete?
I noticed a lot of 1-player games have been shown to be NP-Hard, like Pac-Man, The World's Hardest Game, Tetris, etc.
For PSPACE-Complete, I noticed that Wikipedia listed these 1-player games:
It is ...
- 33
0
votes
1
answer
143
views
Complexity of solving a higher-order degree polynomial equation? P-problem or NP-problem or neither?
I am a mathematician and I am very new to theoretical computer science.
The definition of P/NP problem I found in wiki is that:
P is the set of decision problems solvable in polynomial time by a ...
9
votes
1
answer
286
views
Complexity of permanent verification
Consider the problem of permanent verification:
$\bullet \ $ Given a $n\times n$ matrix $A$ with entries in $\{0,1\}$, and given $k\ge 0$, does $Per(A)=k$?
Question: Is it known to be NP-hard? Should ...
- 812
1
vote
2
answers
95
views
Is Maximum Independent Set polynomial-time solvable in $(p,1)$-colorable graphs for general $p$?
It is well-known that Maximum Independent Set (MIS) in bipartite graphs is polynomial-time solvable.
What happens if we generalize the input graphs by replacing the vertices in one partite with ...
- 421
0
votes
0
answers
70
views
Is this Knapsack/Subset Sum Variant NP-Hard?
The problem: Let $A_1 = \{a^1_1,\ldots,a^1_n\}, A_2 = \{a^2_1,\ldots,a^2_n\}, \ldots, A_k = \{a^k_1,\ldots,a^k_n\} \subset \mathbb{N}$ be $k$ sets of $n$ integers, and let $U,L \in \mathbb{N}$ be ...
- 173
-2
votes
1
answer
218
views
What is the reason to believe that quantum heuristic algorithms can solve NP-Complete problems?
There is an ever going trend to believe that a large number of NP-Complete or NP-Hard problems can be solved using quantum heuristics.
I have observed, a common trend, to take any sort of ...
- 183
0
votes
0
answers
88
views
When Exponential Costs are Essential for NP-Hardness?
In many NP-hard problem there is a budget constraint. Each element $e$ in the instance has a certain cost $c(e)$ and a profit $p(e)$; a feasible solution $S$ for the considered problem cannot exceed ...
- 173
4
votes
0
answers
250
views
Permutation generation problem using swaps
This is motivated by Aaronson's post, Probability of generating a desired permutation by random swaps. I am interested in a related problem where the swaps are given in the input.
We're given as input ...
- 20.8k
1
vote
1
answer
159
views
3 Matroid Intersection, a Special Case
It is well known that finding a maximum cardinality (or weight) common independent set in the intersection of 3 matroids is APX-Hard.
Question: Does this problem remain NP-Hard if one of the matroids ...
- 173
0
votes
0
answers
48
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 ...
- 468
2
votes
1
answer
61
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
93
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 ...
- 123
10
votes
1
answer
432
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,896
0
votes
1
answer
64
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
4
votes
2
answers
193
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 ...
- 421
3
votes
1
answer
138
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 ...
- 33
11
votes
0
answers
160
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,416
13
votes
1
answer
349
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
230
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 ...
user67795
2
votes
0
answers
58
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
129
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,416
4
votes
1
answer
102
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,896
0
votes
1
answer
77
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
152
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
113
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
185
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 ...
- 11.3k
7
votes
1
answer
178
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
3
votes
1
answer
101
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?
- 89
0
votes
0
answers
61
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
72
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
122
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\...
- 81
-1
votes
1
answer
113
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
80
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 ...