# Questions tagged [np-hard]

decision problems that are at least as hard as NP-complete problems

697 questions
Filter by
Sorted by
Tagged with
70 views

### if P=NP, and if language A is not NP-hard, A = ∅ or A = Σ*

I don't know how to solve this. Show that if P=NP, and if language A is not NP-hard, A = ∅ or A = Σ*
52 views

### Maximum independent subset for graphs with lots of edges

Consider an NP-hard graph problem, like the maximum independent set problem. Let us say I restrict my inputs to only be graphs that have $n$ vertices and at least $n^{c}$ edges, for some $c > 1$. ...
41 views

### How can i do this type of swap(4-opt) between 4 edges of a graph?

The double bridge move is a specific type of swap between 4 edges of a graph, also called 4-opt. It consists of removing 2 pairs of edges. Let`s call them (I, I+1), (J, J+1) and (P, P+1), (Q, Q+1). ...
62 views

### Can it be NP hard to calculate the value of a function?

So, I've just begun dabbling in complexity theory and I'm somewhat confused as to the relationship between NP-hardness and function computation. As far as I've understood, NP-hardness is defined for ...
19 views

### Reduction from SAT to EXACTSAT

PROBLEM: EXACTSAT INPUT: A boolean formula $\phi$ in CNF with $n$ variables, and a natural number $k \le n$. OUTPUT: "Yes" if and only if there is truth assignment $\theta$ which sets ...
34 views

### Fastest way to find optimal graph coloring in polynomial space given chromatic number

Suppose I have a graph's chromatic number. Give a faster-than-brute-force polynomial-space algorithm for finding an optimal coloring. If such an algorithm isn't known, please tell me so. This question ...
76 views

### Can we DISPROVE that a problem is NP-complete

So I basically had an exam question in which we were given a problem and we had to prove or disprove that it was in NP-complete. I tried to prove it but could not because apparently it could not be ...
33 views

### Where does each part of the $1 - (1 - 1/k)^k$ approximation for the Maximum Coverage problem come from?

A solution to an instance of the Maximum Coverage problem with a budget of k subsets can be approximated with a greedy algorithm that, at each iteration, picks one of the subsets that adds the most ...
107 views

### If the halting problem is NP hard, would P = NP with a hypercomputer capable of computing the halting problem in polynomial time?

The halting problem is NP hard, to my knowledge any NP problem can be reduced to a NP hard problem. Let us define a new computational complexity class called HP(Hypercomputational polynomal-time), The ...
32 views

### A be an NP-complete problem, and if B be an NP-hard problem. If A is polynomial time solvable then is B is polynomial time solvable?

if A be an NP-complete problem, and if B be an NP-hard problem. If A is polynomial time solvable then is B is polynomial time solvable? on the contrary, if A be an NP-complete problem, and B be an NP-...
28 views

### Prove that T3SAT is NP-Complete

Instance: A boolean formula f(x1, . . . , xn) in 3CNF form, with m clauses labelled C1, . . . , Cm. Is there an assignment to x1, . . . , xn such that every third clause is False and all other clauses ...
27 views

### Is integer multicommodity flow problem is NP-hard?

As Wikipedia states the time complexity of Integer Linear programming(ILP) is NP-hard, so this means integer multicommodity flow problem is also NP-hard?
741 views

### How exactly is the process of showing a problem to be NP-Complete a proof by contradiction?

The steps involved in proving that a problem is NP-Complete are fairly straightforward to follow, it's the logic behind why the proof is valid that's really throwing me for a loop. Okay so an easy one:...
68 views

### Is this set covering problem NP-Hard?

Consider this variant of set covering problem. Input: a collection of sets $S = \{s_1, s_2, \ldots, s_n\}$ and a universal set $U$, in which $s_k \subseteq U$ for all $k$. The problem is, divide $S$ ...
39 views

### chromatic number is np-hard

I'm referring to a question in this book: Algorithms by Jeff Erickson, link:http://jeffe.cs.illinois.edu/teaching/algorithms/notes/J-approx.pdf, in particular, pg.21, Q11. The author mentioned that ...
19 views

### Computational Hardness of the $k$-Partition Problem with identical numbers/objects?

The $k$-Partition Problem is NP hard. I want to know if some slight modification of this problem makes it polynomially solvable. Now consider the set $S=\{a_1,\ldots,a_n\}$ of IDENTICAL numbers/...
22 views

### Relationship between complexity classes W[1]-hard and NP-hard?

If i have a parameterized reduction from multicolored independent set (W[$1$]-hard) to some problem $A$, which take polynomial time. Can i say that problem $A$ is NP-hard? in other words, Is ...
30 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 ...
30 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?
79 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 ...
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 ...
23 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 ...
13 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, ...
35 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-...
69 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 ...
43 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 ...
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 ...
39 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 ...
32 views

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 $... 1answer 29 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 &... 0answers 17 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 ... 0answers 49 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}$... 1answer 646 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 ... 1answer 79 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 ... 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 ... 1answer 66 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 ... 1answer 188 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. ... 0answers 34 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 ... 0answers 88 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 ... 1answer 74 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 ... 2answers 137 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: ... 0answers 55 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 ... 0answers 27 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 ... 0answers 55 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 ... 2answers 134 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 ... 1answer 35 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 ... 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 ... 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 } \...
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 \$...