Questions tagged [np-hard]
decision problems that are at least as hard as NP-complete problems
682
questions
2
votes
1answer
25 views
Why proofs of Cook's Theorem assume k is given (n^k for NTM)?
A typical proof of Cook-Levin's Theorem proceeds like this:
Suppose problem X is in NP. Then there is an NTM M
deciding X in time n^k, for some k. Given a word w,
NTM M, and k, we construct a Boolean ...
-3
votes
1answer
22 views
Proving correctness of Polynomial reduction
Given a problem A is NP-Hard and A ≤𝑝 B, is there a way to prove that B is also NP-Hard?
2
votes
0answers
70 views
Is it NP-hard to find different roots of different matrices simultaneously?
Consider the following problem:
input: pairwise distinct natural numbers $k_1,\dots,k_m$ that are all $\leq n$, and matrices $A_1,\dots,A_m \in \Bbb Q^{n \times n}$ where $m \leq n$.
output: a ...
2
votes
0answers
31 views
Partition columns into m groups to maximize absolute value sums
The Task
You are given $n$ columns each of length $m$. All values are either $-1$ or $1$. Find an assignment $s$ of each of columns to 1 of $m$ groups in order to maximize the sum of all the absolute ...
-4
votes
0answers
22 views
How do we prove this NP hard decision problem?
How can we prove this statement? Based on a formal decision problem it can be solved, right, but how exactly we can define this problem to be proved. I am not getting this concept properly.
A ∈ P if ...
0
votes
1answer
21 views
polynomial time approximation algorithm problem
How can we actually define a polynomial-time 4-approximation algorithm for vertex cover or knapsack problem?
For say we have 2 approximation problems which less than equal 2C*. But when we have a ...
0
votes
0answers
11 views
Need Help Solve an NP problem with an Approximation Algorithm
I have an algorithm problem which I do not know how to solve and I think it is NP-complete. Let me try to explain with a general example.
Given $n$ objects, each with $k$ possible properties, ...
0
votes
1answer
33 views
Does reducing a NP Hard problem to a NP problem make that NP hard problem a NP Complete problem?
I was asked a question in my algorithms exam which had this as the core question after simplifying. I had written that it would be NP-Hard but I got it wrong my professor is saying that it would be NP-...
2
votes
1answer
54 views
Find the class of the problem PP1 and PP2 using the information given below
Assume that P1, P2,..., Pn are all NP-class problems. PP1 and PP2 are unknown problems (i.e., we don't know whether they belong to the P or NP classes). If "P1, P2,...., Pn" problems can be ...
0
votes
1answer
34 views
Subset Sum With Interval Integer Target
Define the subset sum with interval integer target problem (SSIITP) as follows:
SSIITP Input:
A multiset $S = \{a_1, …, a_p\}$ of positive integers $a_i$.
An integer $T$.
SSIITP Output:
True, if ...
1
vote
1answer
28 views
Vertex cover in a special graph
We say that an undirected graph $G=(V, E)$ is special if for every vertex $v\in V$ and edge $\{u, w\}\in E$, it holds that $\{v, u\}\in E$ or $\{v, w\}\in E$. In other words, a graph is special if for ...
0
votes
0answers
32 views
reference that minimum makespan on identical machines is NP-hard?
I need to cite a reference that the minimum makespan problem on ($>2$) identical machines is NP-hard. I've seen Garey and Johnson cited as a reference, but it I'm not sure which of the problems is ...
0
votes
1answer
29 views
Reduction of np to npc
Given that $A$ is $NPC$ problem. And I need to check "if $D$ belongs to $NP$ and $D\leq_p^\mathsf{}A$ then $D$ is $NPC$" is true or not?
My approach: Since $D\leq_p^\mathsf{}A$, therefore $...
1
vote
1answer
26 views
Is the clique problem polynomial-time solvable still in unit disk graphs allowing different sized disks?
Clark et al. proved that the clique problem is polynomial-time solvable in unit disk graphs. Does anyone know if this result holds still if the disks are allowed to be different sizes? Or do such &...
0
votes
0answers
16 views
Complexity class of computation of Homfly polynomial
It is claimed that "the problem of the computation of the homfly polynomial is NP-hard." but is it known if it is NP-complete? By the definition of NP-completeness, wouldn't it be enough to ...
0
votes
0answers
48 views
Accurately determine the real 'hardness' value of any given input instance for subset sum
Assuming the 'hardness' of any possible input instance with $N$ elements (of any bit length) for the subset sum problem could be represented as $H \in \{0,0.000001,0.000002 \dots, 1 \}$, being ${0}$ ...
4
votes
1answer
633 views
Proofs of reduction of any hard problem
Approach:1 To prove any unknown problem $B$ is NPH then take any known NPH problem $A$ (e.g. $3$-sat) which reduces to $R$ in polynomial time. If I take any instance example $I_1$ of $A$, then ...
0
votes
1answer
76 views
Reduction from undecidability, decidability to decididabilty
If given any two language both
$L_1$ and $L_2$ are decidable then why both $L_1\leq_m^\mathsf{}L_2$ and $L_2\leq_m^\mathsf{}L_1$ are false. Please provide easy explanation with any counterexample ...
1
vote
0answers
21 views
Software/library to generate Ising models for random $k$-sat problems
Could someone point me to a software/library which lets one to generate the Ising model/spin model for random $k$-sat problems or $k$-sat problem of a given structure?
I understand that it will be ...
2
votes
1answer
60 views
Unusual MST variant on bipartite graph
On math.se, Sybren Zwetsloot has asked for help with an unusual optimal subtree problem. Here's my understanding of what he's asking:
We have a weighted bipartite graph on two sets $N$ and $B$, call ...
2
votes
1answer
185 views
Topological sort with minimum maximal distance in array
I have a DAG that admits many possible topological sorts. I want to construct one that has the minimum maximum distance between a node and its neighbours in an array storing the nodes in sorted order.
...
1
vote
0answers
32 views
NP-hardness proof of an optimization problem with real values and real input in the decision problem
Question - Let's suppose we have an optimization problem $\mathcal{P}$ with a real-valued measure function and the decision version of the optimization problem $\mathcal{P}_D$ (please see definitions ...
2
votes
0answers
82 views
NP-hardness proof of an optimization problem with real values and rational input in the decision problem
I'm studying complexity theory and I have the below question regarding $NP$-hardness proofs of optimization problems with real values. Any reference is much appreciated.
For the question, take the ...
1
vote
1answer
73 views
Is this variant of the pinwheel scheduling NP-Hard?
I wonder if the following variant of the pinwheel scheduling is NP-Hard.
Given a set of n radars S = {s$_1$, s$_2$... s$_n$} and a set of m areas A = {a$_1$, a$_2$, ... a$_m$}. Each radar s $\in$ S ...
3
votes
2answers
109 views
Subset Sum With Interval Target
Define the subset sum with interval target problem (SSITP) as follows:
SSITP Input:
A multiset $S = \{a_1, …, a_p\}$ of positive integers $a_i$ such that $\sum_{a_i \in S} a_i = T$.
SSITP Output:
...
1
vote
0answers
50 views
Does an FPTAS exist for the multiple subset sum problem when m is fixed and c is not a variable?
From Wikipedia Multiple subset sum: The multiple subset sum problem (MSSP) is a generalization of the subset sum problem (SSP): given a multiset $S$ of $n$ integers, and an integer $m$, the goal is to ...
0
votes
0answers
24 views
Number partition subjected to the cardinality of subset
I hope someone can take some time to consider the following problem and welcome to discuss together.
Number partition problem is one of well-known NP-hard problems.
Now I am considering the hardness ...
0
votes
0answers
48 views
Given a set of integers and target, find all subsets of size k such that sum of elements of each subset equals target
I am trying to solve below problem
Given a set of integers A, and target integer, find all subsets of size k such that sum of elements of subset equals target.
One approach could be enumerating all ...
1
vote
2answers
126 views
Is this explanation confusing NP-hard and NP-complete?
My notes on P vs NP say the following:
Every problem x in the NP-hard class has the following properties:
– There is no known polynomial-time algorithm for x.
– The only known algorithms take ...
0
votes
1answer
34 views
How to prove that the generalized assignment problem (GAP) is NP-hard?
Specifically, what NP-hard problem can we reduce (the decisions version of) GAP to and how do we prove its correctness?
The decision version of the generalized assignment problem is to determine ...
1
vote
0answers
29 views
How to sample the most unique vectors from a very large set efficiently?
While this question already exists and does talk about a heuristic with the Farthest Point First technique, I would like to approach the problem in a more efficient way. I do agree that this is an NP ...
1
vote
0answers
23 views
NP-Hardness of $\{ (S,k) | \exists S' \subset S \text{ s.t } \forall x \neq y \in S' \gcd(x,y)=1 \text{ and } \sum_{s \in S'} s \geq k \}$
I have been practicing NP-Hardness reductions and have been particularly interested in the language $L = \{ (S,k) | \exists S' \subset S \text{ s.t } \forall x \neq y \in S' \gcd(x,y)=1 \text{ and } \...
-2
votes
1answer
55 views
Reducing subsetsum to {<G, l, u> | G is a weighted graph that has a spanning tree with weight between l and u} [duplicate]
How can I reduce Subsetsum (or maybe other np-complete problem) problem to the problem below?
input : a weighted graph $G$ and numbers $l$ and $u$.
output : Does $G$ has spanning tree, $S$, such that $...
1
vote
1answer
70 views
SUBSET SUM reduction to PARTITION
This is the PARTITION problem:
Given a multiset S of positive integers, decide if it can be partitioned into two equal-sum subsets.
This is the SUBSET SUM problem:
Given a multiset S of integers ...
1
vote
1answer
37 views
Why this problem is NP-Hard?
I'm asking about the question described here:
Knapsack Problem with exact required item number constraint
Can't we iterate over $\binom{n}{L}$ options (which is polynomial), and for each option check ...
0
votes
1answer
28 views
Understanding the complexity class of a problem formulation
I'll keep the reasoning abstract.
If I start from a mathematical formulation of a problem $A$ known to be $NP$-hard, I add a set of constraints which creates a problem $A'$.
However, I do know that ...
0
votes
1answer
42 views
Is this variation of Max-Coverage NP-hard?
Setup
An instance of Max-Coverage is typically defined by a collection of $n$ sets $S = \{s_1, s_2, \dots, s_n\}$, and a budget $k$, where the objective is to select a subset $U\subset S$ such that
$$\...
0
votes
0answers
88 views
Algorithm for Variant of 0-1 Knapsack Problem
Variant of 0-1 Knapsack Problem is when you can choose exactly $k$ items from $n$ items, and $k$ is positive integer parameter that came in the input.
Is there an algorithm with running time ...
1
vote
1answer
28 views
Is it NP-hard to check whether for a $k$ there exist both a Cut and a Bisection of value $k$?
Input: An undirected, unweighted graph $G=(V,E)$.
A cut is defined as a partition $V=A\dot\cup B$.
A bisection is defined as a partition $V=A\dot\cup B$ with $|A|=|B|$ if $|V|$ is even (or $|A|= |B|+1$...
1
vote
3answers
139 views
Spanning tree whose sum of edge weights are between two boundries
I saw this problem:
$\langle G,w,k_1,k_2 \rangle \in L$ iff Graph $G$ has a spanning tree whose sum of edge wights are less than $k_2$ and greater than $k_1$. The problem says that we can prove this ...
1
vote
1answer
28 views
Computational complexity of dividing a set of constraints into a minimum number of satisfiable clusters
I am looking for the computational complexity of the following problem.
Divide a given set of constraints into a minimum number of satisfiable clusters such that the constraints within the same ...
2
votes
0answers
32 views
How far would complexity hierarchies collapse if $L\in CoNP$ is $L\in NPH$?
Let $L\in CoNP$. Assuming that $L\in NPH$, what would we get?
So, as $L\in NPH$ then every language $A\in NP$ has a reduction $A \leq L$. This would mean that $\overline{L} \leq L$ as well. By ...
2
votes
1answer
34 views
NP-Hardness of Half-SAT (at least half clauses)
I'm solving Problem 14.14 of What can be computed?.
14.14 Consider the computational problem HALFSAT defined as follows. The
input is a Boolean formula B in CNF. If it is impossible to satisfy at ...
1
vote
0answers
46 views
What computational hardness concept corresponds to strongly-polynomial time algorithms?
Consider the computational problems in which the input is a set of $n$ integers with maximum magnitude $M$. According to Erik Demaine's lecture notes, assuming $P\neq NP$, the following are true:
If ...
1
vote
1answer
33 views
Inapproximability of graph problems on a restricted setting
I am considering the following problem $\mathcal{P}$.
$\mathcal{P}$: Given an undirected graph $G$, and an integer $k$, find a set of vertices $S \subseteq V(G)$, with $|S| = k$, such that the number ...
7
votes
3answers
168 views
Shortest walk in a grid with turnstiles and waypoint
This video shows a grid maze with a type of tile that I'd call turnstiles.
The mechanics of those tiles are described below.
A turnstile tile has two bars on adjacent sides of the tile.
You cannot ...
1
vote
0answers
26 views
Is the problem "find the sequence of $N$ numbers between 1 and $D$ with least cost", NP-hard?
Consider sequences $p=(p_1,\dots,p_N)$ (the order matters) of length $N$, where $p_i\in\{1,\dots,D\}$ for fixed $D$. Moreover, consider a cost function $c:\{1,\dots,D\}^N\to\mathbb{R}$ which comply $c(...
0
votes
1answer
33 views
Is this variation of the traveling salesman problem NP-hard
Consider the following setting. You have $n$ cities, and there is a cost to travel from a city $i$ to a city $j$ given by $c_{ij}>0$ where $c_{ij}\neq c_{ji}$. Moreover, if you are traveling to ...
2
votes
1answer
60 views
How to find long trails in a multidigraph
I have a directed multigraph (a multigraph is a graph that can have more than one edge between any two nodes). In Wikipedia's terminology, this is a directed multigraph (edges without own identity). I ...
0
votes
0answers
43 views
maximal independent set on grid-based graph proof of approximation ratio
We have a G = (V, E, w), in form of a grid graph with a single diagonal line in each grid in form of below. Where w is the V weight.
We use a greedy algorithm that takes in each step maximum weighted ...
