Questions tagged [np-hard]
decision problems that are at least as hard as NP-complete problems
632
questions
1
vote
1answer
68 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
15 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
93 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
80 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
53 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)...
2
votes
0answers
40 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
64 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
1answer
92 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
19 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
68 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
27 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 ...
0
votes
1answer
32 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
30 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
180 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
27 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
60 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
52 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
123 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
39 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 ...
3
votes
1answer
73 views
If a solution to Partition is known to exist, can it be found in polynomial time?
In the Partition problem, there is a set of integers, and the goal is to decide whether it can be partitioned into two sets of equal sum. This problem is known to be NP-complete.
Suppose we are given ...
1
vote
1answer
33 views
Cyclic tour minimizing total weight
I asked the following question on math.se but it wasn't really answered so moved it over here as I feel it's more relevant.
I saw the question below on an old stack exchange question when looking to ...
0
votes
0answers
30 views
Difference longest path problem and underlying decision problem [duplicate]
I am studying the longest path problem with the final objective to show that it is NP-complete. On wikipedia I read that the problem itself is NP-hard but the underlying decision problem is NP-...
1
vote
1answer
43 views
Trapdoor functions that depends only on NP-hard?
As far as I can tell, there are no examples of trapdoor functions which hardness assumptions is merely hardness of some NP-hard problem in worst case. That is, a trapdoor function in which, it is ...
8
votes
2answers
276 views
NP-hardness for one-dimensional facility location problem with entrance fee for each customer
We have $n$ customers, $(x_1, \dots, x_n)$, sorted on the read line. For convenience, we also use $x_i$ to denote its coordinate on the line. We need to locate $m$ facilities on the real line. We note ...
0
votes
0answers
56 views
Is the Maximum Independent Set problem NP-complete? [duplicate]
It can be read on Wikipedia that MIS is NP-hard. However, is it also NP-complete?
This article says:
"Thus, the Maximum Clique Problem(MCP) and the Maximum Independent
Set(MIS) Problem are ...
0
votes
0answers
36 views
Are there any tetrational-time problems?
I know there exists problems decidable in polynomial-time, exponential-time, etc. I couldn't find any tetrational-time problems, however. Are there any and if not, why?
-1
votes
2answers
70 views
NP-hardness language
How to prove that language $L = \{G \; | \; \omega(G) \geq \frac{9}{10}\cdot n\}$, where $n$ - number of vertices in the graph, NP-hard?
$\omega$ - is a clique number.
0
votes
0answers
32 views
How can I prove the following problem is NP?
Because of the covid-19 pandemic, our firm works semi-remote working. We want to that:
Every day 2/5 of staff should be in the office.
Everyone should go to the office 2 times a week.
Teams want to ...
0
votes
0answers
25 views
Is it possible to determine an instance of an NP-hard problem is easy or hard by the optimization?
I have an NP-hard problem and an optimization to deal with the problem.
I want to know that is it possible to distinguish between easy and difficult instances of the problem by the parameters of the ...
0
votes
1answer
34 views
What parameter of optimizations, like time solving, can be used to show a phase transition in NP-hard problems?
Before asking the question, I should say that I am not sure here is a proper community to ask this question or not.
I have an NP-hard problem and an optimization to deal with the problem. Recently, I ...
1
vote
1answer
38 views
NP-hardness of language of graphs with $\alpha(G)=n/3$
How to prove the NP-hardness of the language $\{G \mid \alpha(G) =\frac{1}{3} |V(G)|\}$?
Here $G$ is a graph, $V(G)$ is its vertex set, and $\alpha(G)$ is the independence number of $G$, which is the ...
1
vote
1answer
42 views
3Col reduction Variation, Special edges
I have a question concerning NP reduction.
My question asks me to show that if I have a graph with Edges that connect 3 nodes together instead of 2, (Y style I assume). I need to prove that finding ...
0
votes
1answer
85 views
Proving NP-completeness for a not so cheesy problem
Let's say we have a matrix M[1..B, 1..B] (i.e., a square matrix) and a mouse in the upper left corner (1,1). We also have an integer A, which tells how many pieces of cheese there are in the matrix. ...
0
votes
0answers
35 views
Subset selection with maximum sum and minimum variance?
So I am trying to tackle a combinatorial optimization problem and would like some insights on how to approach it. The problem statement is as follows: Consider a set of elements of size N, how do I ...
2
votes
0answers
50 views
Why do I only need to reduce from one problem in NP to prove NP-Hardness?
Suppose I wish to show that my decision problem $Q$ is NP-Hard. Why do I need to reduce from one problem $Q'$ of known hardness ?
Consider for instance the following situation:
Here, I have my set NP ...
0
votes
0answers
70 views
3-Sat reduction to facility location problem
I'm learning about NP problems and I this problem which is a bit challenging for me.
You are given an undirected, simple graph G = (V,E) and an integer k where nodes represent cities and edges ...
0
votes
0answers
88 views
Reducing 3-SAT to restricted 3-SAT
I am trying to show that the following problem is NP-hard.
Input: A boolean function in CNF (conjunctive normal form) such that every clause has at most three literals and every variable appears in at ...
4
votes
1answer
82 views
Are “pipes” puzzles NP-hard?
Is the decision version (i.e. does a solution exist) of this puzzle NP-hard (for an nxn puzzle)? It feels like it has very local strategies which allow easily solving the instances, but it's not ...
1
vote
0answers
25 views
Modify a binary matrix to minimize the sum of values of the rows
I have a matrix of zeros and ones, i.e., $\mathbf{X}=[x_{ij}]$ with $x_{ij}\in\{0,1\}$ for all $i=1,2,\ldots,m$ and $j=1,2,\ldots,n$. Associated with each row $i$ of the matrix $\mathbf{X}$ a set of ...
1
vote
0answers
32 views
Is Partition Problem with non-integer input NP-complete?
The Partition Problem supposes that we have a set $S=\{s_{i} \in \mathbb{R^{+}}\}_{i=1}^{n}$, is there a subset $T$ such that $\sum_{s \in T} s = \sum_{s \notin T}s$?
I have read a lot of proofs using ...
0
votes
1answer
78 views
Are most machine learning problems the same problem? (NP-hard)
I am trying to teach P vs NP to some primarily Machine Learning folks. I wanted to come up with an introductory fact to grab their attention.
Reasoning for Question:
Most problems in Machine Learning ...
1
vote
1answer
24 views
What is a good reference for NP hardness in the machine learning/optimization/operations research context?
I am reading some papers in machine learning and at the very beginning (introduction) you will see statements of theorems that says, for example:
Theorem 1.1. For any constant ϵ > 0, it is NP-hard ...
0
votes
1answer
56 views
If a poly-time solution exists for an NP-Complete (Decision) problem, then there exists a poly-time solution for the NP-hard (Optimization) flavor?
This question boils down to: If a polynomial time solution exists for a decision problem, is there also a polynomial time solution for the same problems optimization flavor?
Let's take the Traveling ...
0
votes
1answer
81 views
Algorithm for assigning people to groups
Given a list $L = [1, 2, .., n]$ and a list $C = [(L_i, L_j), ....]$ form a group of pairs $G = g_1, ..., g_{n/2}$ such that:
every element of $L$ is assigned to exactly one group
$g_k = (L_i, L_j) \...
4
votes
2answers
67 views
How difficult is this matching-like problem?
Let $A$ and $B$ be two sets of integers with $|A|>|B|$.
Given a map $f: A \rightarrow B$ and $i \in A, j \in B$, let us use the shorthand "$i$ is matched to $j$" if $f(i)=j$. I am ...
1
vote
1answer
47 views
How to find a cut in a graph with additional constraints?
I have a complete undirected graph $G=(V,E)$ with positive non-null rational weights $c:E \to \mathbb{Q}^+_{*}$ on the edges, such that $c(v,v) = 0$ for all $v$, and a subset $C \subset V$.
I would ...
0
votes
1answer
67 views
Hardness of maximizing difference of functions
Suppose that the problem of maximizing a real function $f$ over a certain domain $D$ is NP_HARD. What can be said about the problem of maximizing $f-g$, with $g$ being another function over $D$? Is it ...
2
votes
1answer
73 views
Finding a boolean submatrix isomorphic to a specific fixed set of other boolean matrices
Given a matrix $M$ of certain size $h\times w$, where $h\leq w$, for example $5\times 6$, are also given the following set $B$ of additional all-ones matrices, that I like to call target (b)oxes.
$$
\...
1
vote
3answers
715 views
Is there an NP-hard problem for which no Fixed-Parameter Tractable algorithm exists?
Question
Is there an NP-hard problem for which we can add a parameter1 to create a "natural"2 parametrised problem for which no FPT algorithm exists?
The adding a parameter is needed ...
