# Questions tagged [np-hardness]

Questions related to NP-hardness and NP-completeness.

713 questions
Filter by
Sorted by
Tagged with
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
1 vote
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 ...
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 ...
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)$ ...
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 ...
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 ...
1 vote
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 ...
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 ...
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 ...
1 vote
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 ...
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 ...
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)?
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 ...
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 ...
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 ...
1 vote
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 ...
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 ...
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 ...
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 ...
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 ...
1 vote
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 ...
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 ...
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$,...
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 ...
432 views

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 $\... 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$,... 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 ... 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 ... 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 ... 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 ... 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 ... 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 ... 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 ... 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, ... 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 ... 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 ... 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 ... 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 ... 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 ... 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? 0 votes 0 answers 61 views ### Existence of W-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-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 ... 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\...
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 ...