# Questions tagged [np-hard]

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

736 questions
Filter by
Sorted by
Tagged with
16 views

### Complexity of the feasibility and optimization problems

Given an optimization problem $P$, if we know that this optimization problem is NP-hard, is it necessary to check the complexity of the corresponding feasibility problem, i.e. the complexity of ...
239 views

### How to prove the optimization version problem (whose decision version is NP-complete) can be solved in poly-time iff P=NP?

I have proved the decision version of my problem to be $\mathcal{NP}$-complete. And I know that if I can solve the optimization version in poly-time, then I can just compare the obtained minimum (or ...
1 vote
29 views

### Is there a hypothesized "complete" class of problems between P and NP-hard?

For now, assume that P != NP. Is there a "complete" class of problems between P and NP-hard, and if so, what is it called? The two key words here are between complete By between, I mean ...
1 vote
297 views

### Solve Max 3 color problem using 3 color decision problem

I've been stumped on this question for a while and can't find a solution. How can I find the max 3 colorability of a graph(optimization problem) with 3 colorability (decision problem) without brute ...
1 vote
58 views

30 views

### Do non-linear dynamical systems have the potential to have an edge on other algorithms when it comes to computing NP-complete problems?

In a recent presentation, I've seen the difficulty of NP-complete/NP-hard problems attributed to the fact that they often have "long range" correlations, or at least they can be interpreted ...
1 vote
25 views

44 views

### Is there a polynomial time reduction from B to A in this case?

Suppose we have an NP-complete problem A, an NP-hard problem B, and a polynomial time reduction from A to B exists. Do we have a polynomial time reduction from B to A as a result?
31 views

### NP Completness and NP Hard

i need some help regaridng this text: CLIQUE = { G, k | G is an undirected graph that contains a clique with k nodes } The textbook proves that CLIQUE is NP-complete. Define the language TWO-CLIQUES ...
48 views

### Is the weighted sum of subset prefix product problem NP-hard?

I have this strange problem where we have a set of positive numbers $M$, a fixed number $n$, and a function $f\colon M \rightarrow R^+$ mapping each number in $M$ to another positive number. We want ...
1 vote
18 views

### Why do we round from 1/2 when converting the LP to ILP for the weighted vertex cover problem?

I understand that to approximate a solution to the weighted vertex cover, we need to relax the integer linear program to a linear program which can be solved in polynomial time, but why do we round ...
1 vote
24 views

The problem is defined as https://npcomplete.owu.edu/2014/06/10/exact-cover-by-3-sets/: Given a set $X$, with $|X| = 3q$ (so, the size of $X$ is a multiple of $3$), and a collection $C=\{(x_{i1},x_{... 1 vote 0 answers 18 views ### Extended venn diagram I try to solve a computational problem, but its solution lives on a generalized Venn diagram statement. I was able to obtain its general formula, but now I require some necessary conditions to avoid k ... 0 votes 0 answers 67 views ### Can this kind of NP-Hard problem be approximated? Consider this kind of optimization problem: (1) The problem aims to minimize a value. Let n denote this value. (2) To determine whether n = 0 is a NP-Complete problem. It is obvious that this kind of ... 3 votes 0 answers 61 views ### Low-rank matrix completion is NP-hard In looking into the problem of low-rank matrix completion / relaxations of the general problem to derive exact solutions, many papers cite that the original formulation is NP-hard but I cannot find a ... 3 votes 0 answers 1k views ### Is protein folding really NP-hard and how to show 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 ... 2 votes 2 answers 915 views ### What is a witness string? I unable to understand the concept From the text A language$L$is in the class$NP$iff there exists a polynomial-time Turing machine, denoted$V$, that gets an input string$x$as well as a read-only string called the witness$w$, ... 0 votes 1 answer 20 views ### Algorithm for Wrapping Problem Assume we have n items with each having a different length and m wrappers each has a different length. The cost of every wrapper is proportional to its length. An item can be covered with one or more ... 2 votes 0 answers 32 views ### Maximum Edges Subgraph Given an (undirected) graph$G = (V,E)$with$|V| = 2n$, what is the complexity of the problem of finding the subgraph$G' = (V',E')$with$V' \subset V, |V'| = n$, such that the number of edges$|E'| ...
Given a graph $(V,E)$, I'm interested in embedding it into a Euclidean space $\mathbb{R}^n$ such that each vertex $v\in V$ becomes a point $x_v\in\mathbb{R}^n$ and $d(x_v,x_u) \leq 1$ (Euclidean ...
### Proof of NP-hardness of the k-means clustering problem for $k\geqslant 3$
coming from the computing science side rather than from the data analysis one, I studied the k-means clustering problem for a short time and noticed that the NP-hardness of the problem for $k=2$ seems ...