# Questions tagged [np-hardness]

Questions related to NP-hardness and NP-completeness.

570 questions
Filter by
Sorted by
Tagged with
149 views

### Are there any NP-complete for continuous mathematics? [closed]

Looking at this wiki page, it seems most NP-complete problems are based on discrete structures, such as graphs. What are some problems that involve real or complex analysis instead of discrete ...
155 views

### Is pooling-aware bin packing NP-Hard?

I am unable to prove whether the following problem is NP-Hard. It seems like a bin-packing or a partition problem, without being close enough to either of them (at least I do not see the reduction to ...
31 views

### Sparse coding and matching pursuit algorithms

Is it true that all known sparse coding algorithms which work efficiently in practice don't have convergence proofs and always use an intermediate step of a matching/subspace pursuit algorithm on the ...
27 views

57 views

### Help in NP-Hardness proof of a certain type of Class Cover problem

Class Cover Problem is nothing but finding an optimal cover of certain class (Point Set) with a particular shape only i.e. finding minimum number of a certain shaped polygon (for example, rectangle) ...
278 views

### Partially filled jigsaw puzzle with six types of tiles

This is a slight variation of the question Are 'zero-one' jigsaw puzzles NP-complete? asked on cs.stackexchange.com. What is the complexity of the following problem? Input: an $n\times n$ Jigsaw ...
241 views

### What are the consequences of a ${\bf O}$(m) algorithm for SAT

We are given a Boolean formula $F$ in conjunctive normal form with $n$ variables and $m$ clauses and we would like to know if there exists at least one assignment to the $n$ variables that makes $F$ ...
302 views

### NP-Completeness of Certain Bounded Degree Graphs [closed]

I was studying time complexity when it comes to bounded degree graph problems and I was wondering if I can get help with the following two problems. 1) Is the set of all (G, k) where G is a graph ...
373 views

### Hardness of min-max problems

Consider the following min-max problem Given a graph $G=(V,E)$ and an integer $k \geq 0$, delete at most $k$ nodes in $G$ to maximize the size of the minimum dominating set in the residual graph. ...
1k views

407 views

### Hardness of an extended maximum set packing problem

(Edited) The maximum set packing problem when the sets are all of equal size, say $k$, is known to be NP-hard for $k \ge 3$. The requirement in this problem is that the sets in the solution will be ...
596 views

### Comparing graphs

I am looking for a kick in the right direction. What i am trying to do is to compute "similarity" between two graphs, where I define "similarity" as the number of shared paths. example: ...
76 views

### Constrained Topological Sorting with bounded number of chains

In general, constrained topological sorting is NP-hard. Now we add another constraint to it, such that take any k+1 nodes and there will be at least one pair ...
250 views

### PTAS (polynomial time approximatin scheme) for euclidean TSP/Minimum-Cost k-Connected subgraph problem

Problem 1 I have read "On Approximation of the Minimum-Cost k-Connected Spanning Subgraph Problem" (by A. Czumaj, A. Lingas), and even in the abstract are 2 statements "We present a polynomial time ...
76 views

### Is the counting version of 1-in-3 Sat #P-complete?

In the paper "Hard Tiling Problems with Simple Tiles", Moore and Robson prove that Cubic Planar Positive 1-in-3 Sat in NP-complete by a reduction from Positive 1-in-3 Sat. Cubic Planar Positive 1-in-...
69 views

### About using smoothness of the Hessian for getting to approximate criticality of a non-convex objective

Is there any algorithm which shows that under the assumption of Lipschitz smoothness of the Hessian of a non-convex function one can get to its critical point faster?
226 views

### Is there any reference on the hardness of approximation for 2-partition problem?

I tried to look for some references but could not find any. I knew it is proved to be NP-complete via a transformation from Knapsack or 3DM problem. But I couldn't find a way to apply PCP theorem to ...
75 views

### NP-Hard Knapsack Instances

Consider the classic Knapsack optimization problem (KP): Given $p_1, \dots, p_n, w_1, \dots, w_n, B\in\mathbb N$, compute a solution $I\subseteq \{1,\dots,n\}$, such that $\sum_{i\in I} w_i \leq B$ ...
45 views

### Complexity of multi-objective optimization problems

How can we define and prove the worst-case complexity of multi-objective optimization problems (MOOP)? It is easy to see that, if one of the objectives is an NP-Hard optimization problem, then the ...
101 views

### Network Reliability Problem

Network reliability, in which we are given an undirected graph $G$ with a failure probability $p_e$ for each edge and we are asked to calculate the probability that the network becomes disconnected ...
62 views

### Generalization of k-Coloring: maximizing the number of vertices with no neighbours of same color

One can consider the following generalization of the $k$-Coloring problem: Let be given a graph $G$ and an two integers $k$ and $p$. A vertex $v$ of $G$ is properly colored if $v$ has no neighbour ...
60 views

### About complexity of recovering or learning Bayesian networks

Are there complexity theoretic results about recoverability or learnability of the marginals (of the source vertices) and the conditionals (along each of the edges) of a Bayesian network from having ...
33 views

### On approx-preserving P- and A-reducibilities

Let $X$ and $Y$ be two NPO problems. Let $(f,g)$ be a reduction between $X$ and $Y$, in particular, assume that $(f,g)$ is both P-reduction and A-reduction, i.e., there exist two poly-time ...
154 views

### NP-hardness of minimizing sum of complicated objective function

In our research, we faced the following problem optimization problem: Input: a list of $k$ pairs of positive integers $(n_1,d_1), \ldots, (n_k,d_k)$; an integer $m$. Output: $P$, a partition of the ...
443 views

### Hardness of Minimizing Submodular Functions with Cardinality Constraints

I am new to submodular functions and I am reading the introductions to submodular functions and applications ( https://www.ima.umn.edu/optimization/seminar/queyranne.pdf ). In this introduction, it ...
70 views

### Finding exact value with a quotients of products of random values

Sorry for the haphazard title: really not sure what this should be called Suppose we have a set of $z$ random values $S = r_1, \dots, r_z$ drawn from $\mathbb{Z}_N$ (where $N$ is some large prime). ...
112 views

### Minimum Weight Ordering of nodes on a directed graph

I'm bumping my head against the wall trying to prove this problem is NP-complete (it might not be) Let $G = (V,E)$ be a directed graph with weights $w:E \to \mathbb{R_{\geq 0}}$ on the edges. The ...
761 views

### Algorithm to maximize profit: ways to solve/approach? (Advanced NP-Complete)

This one's hard, so all help really appreciated! I know it is NP-Complete and thus cannot be solved in polynomial time, but looking for help in analysis, i.e. what type of NP-Complete problem it ...
353 views

### Maximize Covering Minimizing the Overlap

I have this problem: Given a collection of sets $S:\{S_{1},...,S_{k}\}$ where each set $S_{j}$ is a subset of $U:\{e_{1},...,e_{n}\}$ universe of elements. I would find-out a subset $C \subseteq S$ ...
225 views

### Does coNP-hardness imply NP-hardness [duplicate]

Possible Duplicate: Do many-one reductions and Turing reductions define the same class NPC Hi, Is the following true: If L is coNP-hard, then L is NP-hard. I have found statements of this, ...