Questions tagged [np-hard]
decision problems that are at least as hard as NP-complete problems
657
questions
0
votes
0answers
14 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
27 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 ...
-4
votes
0answers
54 views
Are approximations to $#P$ gibberish? [closed]
approximations to #P are gibberish
the model count in satisfiability (#P) implies straightforward
access to a vast empire inside the logic of truth including
N Boolean variables in a formula with N ...
1
vote
0answers
19 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 } \...
-1
votes
1answer
35 views
Reducing subsetsum to {<G, l, u> | G is a weighted graph that has a spanning tree with weight between l and u}
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
38 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
34 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
36 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
$$\...
-5
votes
0answers
56 views
VS Problem algorithm
In CLOSED VERTEX COVER, we are given a graph G In CLOSED VERTEX COVER, we are given a graph 𝐺 where each vertex 𝑣∈𝑉(𝐺) has self-utility 𝑢𝑣∈ℕ and self-pollution 𝑝𝑣∈ℕ, and 𝑘,𝑈⋆,𝑃⋆∈ℕ.
For each ...
0
votes
0answers
81 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
26 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
96 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
25 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
29 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
24 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
43 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
32 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
152 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
28 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
44 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
33 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 ...
0
votes
1answer
24 views
maximal independent set on grid graph proof
I'm trying to figure out proof of maximum independent set from: this link. (1b part).
And I'm bit confused why exactly sum of $w(v)$ is less than or equal to sum of $w(v')$.
Shouldn't it be other way ...
4
votes
4answers
3k views
Is there any NP-hard problem which was proven to be solved in polynomial time or at least close to polynomial time?
I know this could be a strange question. But was there any algorithm ever found to compute an NP-problem, whether it be hard or complete, in polynomial time. I know this dabbles into the "does P=...
1
vote
2answers
49 views
Proving a problem is NP Hard
Consider the following problem: Given a weighted directed graph $G$, determine if $G$ has a cycle whose total weight is $k$. All edge weights are integer but might be negative. $k$ is not an inputted ...
17
votes
4answers
4k views
Is the following problem NP-hard? (or have you seen it before?)
I genuinely don't know if the following problem is NP-hard. I have never seen it mentioned online, but it's hard to even search for exact problems like this. I have been trying to find an efficient ...
0
votes
1answer
19 views
Given N positive integers are they the integers 1-N : What is the relationship between this problem and NP?
Here’s the decision problem:
Suppose I have N positive integers encoded in base-2 (as oppose to unary)
Are these integers precisely the integers 1-N in some order?
This is related to the Hamiltonian ...
1
vote
1answer
98 views
k disjoint triangles with graph splitting to two distinct groups
Please note that this question is different than this question.
The $k$-disjoint triangles problem is as follows:
Input: A graph $G=(V,E)$ and an integer $k\in \mathbb{N}$
Output: Are there $k$ ...
0
votes
1answer
26 views
Are problems that are fractions of constraints of NP-complete problems also NP-complete?
We know that Hamiltonian path, clique and independent sets are NP-complete but what about half or the square root of each problem or a fraction of $n$ ? That is, for a graph, $G$ of $n$ nodes,
is ...
1
vote
1answer
75 views
How to prove NP-completeness of this mail-problem?
Let's say we have n postmen that are bringing people mail in a neighbourhood, and that they start and end at the same post office. This situation can be decribed with a directed graph, where the ...
0
votes
1answer
19 views
Clarification for binary search in solving optimal TSP when a polynomial algorithm with a budge exists
Below is Question 8.1 in Algorithms by Dasgupta et al.
There's a solution to this problem that uses binary search from here. Pasting the answer for posterity.
My questions are:
When they say input ...
2
votes
2answers
111 views
Proving NP-hardness of Hamiltonian Cycle problem variant
I need to prove that determining whether a graph has a relaxed-Hamiltonian cycle (definition given ahead) is NP-hard.
A relaxed-Hamiltonian cycle in $G$ is a closed walk $C$ that visits every vertex ...
-2
votes
2answers
109 views
Does NP-hard problems have to be decision problems? (What the fact please) (contradicting answers)
Let me explain my trouble by another example.
The wiki page says that
Lattice problems are an example of NP-hard problems
However, by clicking NP-hard, i find this definition
A decision problem H ...
-1
votes
1answer
59 views
Clique is NP hard to approximate up to $n^{a}$ for some $a \in (0,1)$
Given that
$\mathsf{NP}=\mathsf{PCP}_{[\frac{1}{n},1]}\left(O\left(\log n\right),\left(O(\log n\right)\right)$,
show that it is NP-hard to approximate clique up to factor of $n^a$ for some $a \in (0,1)...
1
vote
0answers
41 views
Is n-dimentional assignment problem for points NP-hard?
We have $n$ sets of $k$ points in $\mathbb R^d$ and we are trying to partition them to $k$ clusters of $n$ points such that from each set every point is mapped to a different cluster and the sum of ...
2
votes
1answer
69 views
Sub-exponential time algorithm to compute playoff chances
There are 10 teams, Team A through Team J, playing in a triple round robin pool (each team plays thrice against each other team, for a total of a 27 games per team). After the round robin pool, the ...
6
votes
2answers
112 views
Minimum set cover with incompatible sets
I'm interested in a variant of minimum set cover where some sets are ``incompatible'' (they can't be chosen simultaneously).
To state it more formally:
We have a finite base set $X$ and a family $\...
0
votes
0answers
20 views
Does having a similar constraint while reducing a problem to similar problem to prove np hard means they are same?
I have been trying to find the computational complexity of my optimization problem and found that it is Np-Hard. To prove it to Np-Hard, I try reducing it Nurse Scheduling Problem. I am quite confused ...
4
votes
1answer
71 views
Bin packing when items can be broken
In the bin packing problem, there are some $m$ items of size less than $1$, and they have to be packed into as few as possible bins of size $1$. The problem is NP-hard, but if we are allowed to break ...
1
vote
1answer
28 views
The concept of the creation of a trapdoor in NP-complete or NP-hard problems
I am reading the book An Introduction to Mathematical Cryptography. In its chapter 7, there is the following statement:
In real world scenarios, cryptosystems based on NP-hard or NP-complete problems ...
1
vote
1answer
47 views
Why is crossing paths bad in Traveling Salesman?
I'm learning about Traveling Salesman in an online course (sorry I can't share the link it's paid only) and the first step to solving it then just state "as a heuristic we avoid crossed paths&...
1
vote
1answer
34 views
Must an optimization problem with a greedy algorithm belong to P?
If it is known that for some optimization problem there is a greedy algorithm that solves it and the solution includes sorting of input at the preliminary stage, is it necessarily true that the ...
4
votes
3answers
201 views
Algorithm for solving a mixed integer programming problem in polynomial time?
I have the following mixed integer programming (MIP) problem:
$$
\begin{array}{rll}
\text{Maximize } & z=k \\
\text{subject to }
& a_ik - m_i \geq 0 & (i=1,\dots,n) \\
& b_ik - m_i \...
0
votes
1answer
30 views
Reducing the Hamiltonian cycle to the travelling salesman problem and self loops
If this is my adjacency matrix for the hamiltonian cycle:
$$\begin{pmatrix}0&1&0&1\\ 1&0&1&0\\ 0&1&0&1\\ 1&0&1&0\end{pmatrix}$$
Then a reduction ...
14
votes
1answer
3k views
Hardness of a problem which is the sum of two NP-Hard problems
Consider the problem of computing an exponential sum over a certain function $g(x)=f(x)+h(x)$, that is computing
$$\sum_{x}g(x)=\sum_{x}f(x)+\sum_{x}h(x)$$
now if we know that $\sum_{x}f(x)$ and $\...
2
votes
0answers
61 views
P/NP - Proof that SAT-TM is NP-complete uses certificate
To prove that SAT-TM (Turing machine emulating the satisfiability problem) is NP-Hard
$$\text{SAT-TM}:=\{⟨M,p,1^k⟩ \; | \;∃c,\; |c|\leq p(k), \;\text{such that M accepts c in ≤k steps}\}$$
my ...
1
vote
0answers
53 views
any hope to solve np hard problem using deep learning? [duplicate]
I know some basic machine learning and deep learning. Now a days deep learning solve many types of problem. I working working optimization problem like np, np hard problem. Is there any hope to solve ...
0
votes
2answers
228 views
Is Bitcoin mining NP-Hard?
I can't find this anywhere online. Is bitcoin mining NP-Hard?
If so, how would we be able to prove a reduction from a known NP-hard problem? I am a bit lost.
0
votes
0answers
41 views
A multidimensional “moving van problem”: a mix of a knapsack and a bin-packing problem
This problem is a mix of the bin-packing and the knapsack problems. I call it "the moving van problem": there is a moving van with a limit on the weight it can transport, and a set of boxes ...
