Questions tagged [np-hard]

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

Filter by
Sorted by
Tagged with
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. ...

1
2 3 4 5
13