Questions tagged [np-hard]

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

Filter by
Sorted by
Tagged with
-1
votes
1answer
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 = Σ*
2
votes
1answer
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$. ...
0
votes
1answer
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). ...
3
votes
1answer
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 ...
0
votes
0answers
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 ...
1
vote
1answer
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 ...
0
votes
2answers
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 ...
1
vote
1answer
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 ...
-2
votes
2answers
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 ...
1
vote
1answer
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-...
-1
votes
1answer
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 ...
0
votes
1answer
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?
1
vote
3answers
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:...
2
votes
1answer
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$ ...
0
votes
1answer
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 ...
1
vote
0answers
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/...
1
vote
0answers
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 ...
2
votes
1answer
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 ...
-4
votes
1answer
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?
2
votes
0answers
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 ...
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 ...
0
votes
1answer
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 ...
0
votes
0answers
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, ...
0
votes
1answer
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-...
2
votes
1answer
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 ...
0
votes
1answer
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 ...
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
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 ...
0
votes
1answer
32 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
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 &...
0
votes
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 ...
0
votes
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}$ ...
4
votes
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 ...
0
votes
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 ...
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
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 ...
2
votes
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. ...
1
vote
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 ...
2
votes
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 ...
1
vote
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 ...
3
votes
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: ...
1
vote
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 ...
0
votes
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 ...
0
votes
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 ...
1
vote
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 ...
0
votes
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 ...
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
68 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
102 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
2 3 4 5
14