# Questions tagged [np-hardness]

Questions related to NP-hardness and NP-completeness.

544 questions
Filter by
Sorted by
Tagged with
3k views

### Natural CLIQUE to k-Color reduction

There is clearly a reduction from CLIQUE to k-Color because they're both NP-Complete. In fact, I can construct one by composing a reduction from CLIQUE to 3-SAT with a reduction from 3-SAT to k-Color. ...
168 views

### bounded outdegree bipartite spanners

Given an undirected graph $G = (V,E)$ and an integer $k > 0$, our objective is to find a subgraph $G' = (V ,E')$ where $E' \subseteq E$ such that $G'$ has the three following properties : $G'$ ...
2k views

### Is there a natural problem on the naturals that is NP-complete?

Any natural number can be regarded as a bit sequence, so inputting a natural number is the same as inputting a 0-1 sequence, so NP-complete problems with natural inputs obviously exist. But are there ...
404 views

### Is this multiprocessor scheduling problem with overlaps NP-Hard?

The problem statement is: "Given a set $J$ of jobs where job $J_i$ has length $L_i$ and a number of processors $m$, jobs have inter-overlapping (For example, if job $J_i$ and $J_k$ are assigned to the ...
740 views

### What is the complexity of rectangle packing when rotations are allowed?

In the rectangle packing problem, one is given a set of rectangles $\{r_1,\dots,r_n\}$ and bounding rectangle $R$. The task is to find a placement of $r_1,\ldots,r_n$ inside $R$ such that none of ...
4k views

338 views

### Two matrices related by a permutation $B = P A P^T$ - complexity

What is computational complexity of the following problem: given two complex $n\times n$ matrices $A$ and $B$ check if there is a permutation matrix $P$ such that: $$B = P A P^T.$$ If it helps, one ...
969 views

### Complexity of Portal 2

I am studying the complexity of Portal 2 and I would like to know if the problem has been studied before. In particular, I would be interested any reference discussing the complexity of Portal 2 and ...
333 views

296 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 ...
474 views

278 views

### Hamilton Decomposition Decision Problem

Let $G=(V,E)$ be an undirected graph. A decomposition of $V$ into disjoint subsets $V_i$ is called a Hamilton decomposition of $G$ if the subgraph induced by each set $V_i$ is either a Hamilton graph ...
575 views

### Simplest proof of NP-completeness

The only first-principles "proof" that a problem is NP-complete I encountered is from Introduction to algorithms, and deals with the circuit-satisfiability problem. According to the authors, many ...
219 views

### NP-completeness of a problem using a “T-gadget”

Working on a problem I came up with the following "T-gadget": It has 3 connectors (A, B, C); each connector has two wires (A1,A2; B1,B2; C1,C2); it can be rotated (0, 90, 180, 270 degrees); two ...
499 views

### Is this optimum travelling problem under deadlines NP-hard on trees?

One of my friends asks me the following scheduling problem on tree. I find it is very clean and interesting. Is there any reference for it? Problem: There is a tree $T(V,E)$, each edge has symmetric ...
300 views

### reduction of maximum independet set to minimum distance of code

Is there a reference for direct reduction of computing maximum independent set of a suitably constructed graph to computing minimum distance of a linear code when the code is specified by its parity ...
753 views

### What progress has been made to prove whether or not p=np? [closed]

I know that it is still one of the biggest mysteries of computer science whether non-deterministically polynomial problems can be solved in polynomial time. I am curious to know what makes this ...
### Implications of unprovability of $P\neq NP$
I was reading "Is P Versus NP Formally Independent?" but I got puzzled. It is widely believed in complexity theory that $\mathsf{P} \neq \mathsf{NP}$. My question is about what if this is not ...
I am looking for some approximate algorithm with upper/lower bound for the following problem: Given a set of positive integers $\{a_1, a_2, \dots, a_n\}$, partition $\{1, 2, \dots, n\}$ into disjoint ...