Questions tagged [np-hard]
decision problems that are at least as hard as NP-complete problems
617
questions
2
votes
0answers
49 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
69 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
34 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
70 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
32 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 ...
1
vote
0answers
29 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
36 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 ...
9
votes
2answers
253 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
39 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
67 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
27 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
28 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
78 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
26 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
48 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
65 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
23 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
80 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
23 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
30 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
66 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
23 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
42 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
40 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
66 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
40 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
693 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 ...
2
votes
2answers
434 views
Definition of NP-hardness for non-decision problems
As I understand, the term "NP-hardness" is applicable when we also talk about optimization or search problems (i.e. return the satisfying assignment for 3-SAT). How do we formally define NP-...
2
votes
1answer
123 views
If P=NP, does this imply that all problems are NP-hard?
A problem is said to be NP-hard if every problem in NP is reducible to that problem in polynomial time.
Hence, if P=NP, wouldn't that imply that every problem in NP is reducible to every possible ...
0
votes
0answers
19 views
Offline bin-packaging problem: probability of a non-optimal solution for the first-fit-decreasing algorithm
For the offline bin packaging problem (non-bounded number of bins, where each bin has a fixed size, and a input with known size that can be sorted beforehand), the first-fit-decreasing algorithm (FFD) ...
0
votes
1answer
28 views
Multi-dimensional Knapsack with Minimum Value constraints for Dimensions
In MDK, we have a vector $W = \{W_1, W_2, ..., W_d\}$ where each element corresponds to the maximum weight for the respective dimension in the knapsack.
I want to add a conditional constraint: $V = {...
0
votes
0answers
47 views
Is a or free SAT formula NP complete?
Let $L$ be the languague which contains all satisfiable formulas which do not have the or symbol $\lor $.
Or more precise $$L=\{\phi | \phi \text{ is a satisfable formula which is only using the ...
4
votes
1answer
69 views
Algorithm to compute average length of a simple path
Given a connected graph and two nodes s and t, there can be many different simple paths (without cycles) from s to t. Is there an efficient algorithm to find the average length of these paths?
2
votes
2answers
146 views
Is $EVEN-SAT$ $NP$-hard?
I'm looking for an $NP$-hardness proof for the following variant of $SAT$:
$$
EVEN-SAT = \{\langle \phi \rangle: \phi \text{ has an even number of satisfying assignments}\}
$$
I've been playing around ...
1
vote
1answer
185 views
Is protein folding NP-hard and how to prove that?
This question has two facets that are related.
Is the general problem of protein folding really NP-hard?
The hydrophobic-polar protein folding model (Ken Dill et al., 1985) stated the problem on a ...
7
votes
1answer
255 views
Is the buckets of water problem in NP?
Continuing from this question: the buckets of water problem.
(All the definitions can be found there, so I will not repeat them).
As seen there by Yuval's answer, the problem is NP-Hard.
I was ...
2
votes
1answer
182 views
Proof for NP-hardness of simultaneous minimization and maximization of a weighted subset
I am working on a problem defined as the following
Given a set of $n$ elements called $R \subseteq \mathbb{N} \times \mathbb{N}$ and numbers $Z,G \in \mathbb{N}$, where $Z$ is a measure of our ...
2
votes
2answers
73 views
Is realization of unit disk graphs hard?
It is known that recognizing a unit disk graph is NP-hard [1].
However, the paper does not mention how hard the realization problem is.
I have looked up several references [2][3][4]. None of the ...
0
votes
0answers
56 views
Find every path that passes through certain edges
I'm faced with the following problem:
Given
Directed and unweighted graph, where each edge E has two attributes
Goal
Find every path through the 3 (or more) given edges in a specific order
...
0
votes
1answer
84 views
What complexity class is the TSP problem?
Is the travelling salesman problem (TSP) $FNP$-complete or is it $FP^{NP}$-complete?
0
votes
0answers
17 views
Given L1 and L2 in NP, if L1 transforms L2 and L2 transforms HC then L1 NP complete?
Why this Question is False ?
NP-complete problems are the hardest problems in NP.
if L is in NP-complete then [L must be in NP, all problems in NP can be transformed to L].
Does this mean that L2 ...
0
votes
1answer
144 views
How to prove NP-Completeness of longest path between two vertices relying Hamilton NP-Hard problem
I have this question: I have an undirected graph G(V, E) (where V = set of vertices, E = set of edges). Consider the maximum path between two vertices s and t:
...
5
votes
1answer
66 views
Minimizing $\sum_{i=1}^n x_i/y_i$ over a polytope
I want to solve a linear programming problem in the $2n$ variables $x_1, \ldots, x_n$ and $y_1, \ldots, y_n$ where the cost is of the form $x_1/y_1 + \cdots + x_n/y_n$. Specifically, I want to solve
\...
4
votes
1answer
206 views
Prove finding k disjoint paths from n given paths in a directed graph is NP-complete
Problem: Given n paths in a directed graph G(V, E) and an integer k, find out k paths among them such that no two of them pass through a common node.
Prove that the given problem is in NP-complete.
...
