Questions related to NP-hardness and NP-completeness.
17
votes
2answers
363 views
Can you identify the sum of two permutations in polynomial time?
There were two questions asked recently on cs.se which were either related to or had a special case equivalent to the following question:
Suppose you have a sequence $a_1, a_2, \ldots a_n$ of $n$ ...
10
votes
1answer
127 views
What is the minimum required depth of reductions for NP-hardness of SAT?
As everyone knows,
SAT is complete for $\mathsf{NP}$ w.r.t. polynomial-time many-one reductions.
It is still complete w.r.t. $\mathsf{AC^0}$ many-one reductions.
My questions is what is the minimum ...
3
votes
1answer
88 views
The computational complexity of spectral norm of a matrix
How hard is computing the spectral norm of a matrix? This paper says,
... it suffices to say that, except for few particular cases, the Matrix
Norm problem is NP-hard.
I expected that the ...
4
votes
1answer
152 views
What is complexity of this max-edge subgraph problem?
While discussing the question I had asked here, @NealYoung and I encounter another problem, which is to judge complexity of the problem below:
Given a connected undirected graph, finding a ...
-4
votes
0answers
42 views
CoNp!=NP then P!=NP [migrated]
I am new here, and new in theory of complexity in general, this question is a part of a homework that I have got and I was stuck on it, does anyone has the answer? I need it to prepare for the exam.
...
-3
votes
0answers
32 views
how to prove this unsolvable problem about halting problem (turing machine) [migrated]
Show that the problem of deciding, for a given TM M, whether M halts for all inputs within n^2(namely n square ) steps(n is the length of the input) is unsolvable. You can use the fact without proof ...
7
votes
3answers
373 views
Could there be an extremely large hidden subset of Polynomially solvable problems within NP-Complete problems?
Suppose P != NP.
We know that we can make easy instances of 3-SAT at any time. We can also generate what we believe to be hard instances (because our algorithms can't solve them quickly). Is there ...
-4
votes
0answers
46 views
Start using SAT Solvers [migrated]
What i actually want to do is to turn a math problem ,i have to solve,to a Boolean Satisfiability problem and solve it using a SAT Solver.
I wonder if someone knows any manual,guide or anything that ...
7
votes
0answers
112 views
Complexity of interval cover problem
Consider the following problem $Q$: We are given an integer $n$, and $k$ intervals $[l_i,r_i]$ with $1\leq l_i\leq r_i\leq 2n$. We are also given $2n$ integers $d_1,…,d_{2n}\geq 0$. The task is to ...
10
votes
0answers
239 views
Complexity of the densest k-subgraph problem on planar graphs
In the densest k-subgraph problem, one is given an undirected graph $G$ and wants to find a set of vertices $N$ with $|N| = k$ such that the number of edges in the subgraph of $G$ induced by $N$ is ...
0
votes
1answer
60 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 ...
6
votes
2answers
301 views
Decision problem related to coloring
Given a $k$-colorable graph $G$ and vertices $u$ and $v$ of $G$, what is the complexity of deciding if every $k$-coloring of $G$ must assign the same color to both $u$ and $v$?
It does not seem ...
12
votes
1answer
338 views
What is the complexity of this edge coloring problem?
Recently, I have encountered the following variant of edge coloring.
Given a connected undirected graph, find a coloring of the edges that uses the maximum number of colors while also satisfying ...
23
votes
2answers
2k views
Reference for NP-hardness of 3-colouring?
I have a historical question.
I’m trying to determine the reference for the fact that 3-colourability of graphs (alternatively, $k$-colourability for given $k\geq 3$) is NP-hard.
The tempting answer ...
0
votes
1answer
79 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 ...
2
votes
0answers
80 views
Reduction from OR-SAT to Exact CNF-SAT, keeping the number of variables polynomially bounded?
Let me define both the problems first:
$OR$-$SAT$: $m$ Boolean formulae are given in $CNF$, $\phi_1$,$\phi_2$, $\ldots$, $\phi_m$, each on variable set, $x_1, x_2, \ldots, x_n$. ($m$ $<$ $2^n$, ...
2
votes
1answer
135 views
Complexity reductions to Hamiltonian Path?
I am looking for a NP-hardness reduction from an arbitrary problem to the Hamiltonian Path problem such that the reduced no-instances of Hamiltonian path are "far" from having a Hamiltonian path.
Do ...
6
votes
3answers
604 views
The Drawing Challenge - a problem I made up and can't solve!
I made up the following problem but have not made any headway in solving it in anything less than exponential time. Hopefully somebody can shed some light on it. I'm starting to think it may be ...
12
votes
1answer
537 views
How can a problem be in NP, be NP-hard and not NP-complete?
For the longest time I have thought that a problem was NP-complete if it is both (1) NP-hard and (2) is in NP.
However, in the famous paper "The ellipsoid method and its consequences in ...
6
votes
1answer
375 views
How hard is binary Sudoku puzzle?
Sudoku is a well-known puzzle that is NP-complete. Binary Sudoku is a variant that only allows the numbers $0$ and $1$. The rules are as follows.
Each row and each column must contain an equal ...
2
votes
0answers
62 views
Small area containing large amount of patterns
The problem:
I come across a theoretical problem when designing characters for electron-Beam lithography. Abstractly, given an integer $m$, let $\mathcal{M}$ be the set of $(0,1)$-matrix $A_{p\times ...
3
votes
0answers
102 views
Slightly Faster Exponential Algorithm for Integer Programming with Multi-linear Variables
Integer programing is one of the most narutal optimization tools.
As an analogy of DNF or CNF in the Boolean function theory, we can consider the following equation.
$x_{1}x_{2}x_{3}+$ ...
10
votes
3answers
390 views
Subset sum vs. Subset product (strong vs. weak NP hardness)
I was hoping that some one might be able to explain to me why exactly the subset product problem is strongly NP-hard while the subset sum problem is weakly NP-hard.
Subset Sum: Given $X = ...
4
votes
2answers
449 views
P vs NP: Instructive example of when Brute Force search can be avoided
To be able to explain the P vs NP problem to non-mathematicians I would like to have a pedagogical example of when Brute Force-search can be avoided. The problem should ideally be immediately ...
9
votes
0answers
356 views
Intermediate $\mathsf{NP}$-complete problems?
Partition problem is weakly NP-complete since it has polynomial (pseudo-polynomial) time algorithm if input integers are bounded by some polynomial. However, 3-Partition is strongly NP-complete ...
1
vote
0answers
207 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$ ...
7
votes
1answer
150 views
Fitting minimum number of rectangles of width/height 1 into a 2D grid
Consider a problem in which you are given a 2D grid (e.g. a chessboard) where certain squares are occupied
and you need to put the minimum number of non-overlapping rectangles of any size w x h where ...
6
votes
1answer
202 views
$NP$-hardness of scheduling problem
I have been attempting to show that this problem is $NP$-complete but haven't been successful. I wonder if anyone has a suggestion for a problem I could reduce to it.
$CALLS$: Suppose we have ...
14
votes
1answer
185 views
Natural candidates for the hierarchy inside NPI
Let's assume that $\mathsf{P} \neq \mathsf{NP}$. $\mathsf{NPI}$ is the class of problems in $\mathsf{NP}$ which are neither in $\mathsf{P}$ nor in $\mathsf{NP}$-hard. You can find a list of problems ...
2
votes
0answers
139 views
listing of strongly NP problems
I am looking for strongly NP hard problems for a reduction.
So far I have found the following problems:
3-partition problem
bin-packing problem
Numerical 3-dimensional matching
TSP
Any NP-complete ...
4
votes
1answer
206 views
Computational Complexity of Computer Vision Problems
What is the computational complexity of computer vision problems (reconstruction, detection, etc.)? Are these problems NP-complete? Are they NP-hard?
In most cases this will boil down to determining ...
5
votes
0answers
122 views
Universal tractable problem solver
Consider $X$ an $\mathsf{NP}$-complete language e.g. $3-SAT$. I'm looking for an algorithm $A$ for solving $X$ with the following property. Given $M \subset \lbrace 0, 1 \rbrace^*$ any set of words ...
7
votes
1answer
312 views
Does every Turing-recognizable undecidable language have a NP-complete subset?
Does every Turing-recognizable undecidable language have a NP-complete subset?
The question could be seen as a stronger version of the fact that every infinite Turing-recognizable language has an ...
2
votes
0answers
130 views
Is this variation of the “sequencing with release times and deadlines” problem NP-complete?
The following problem is known to be NP-complete. It can be found in pages 236 and 70 of Garey & Johnson. In this book this problem is known either as ...
3
votes
1answer
77 views
Is there an algorithm that's “like” cross-validation for approximation algorithms of NP-hard problems?
I normally do machine learning work, and when I'm evaluating an algorithm on a data set, I always use cross-validation to determine how effective the algorithm is. Is there a similar method for ...
15
votes
1answer
443 views
When does “X is NP-complete” imply “#X is #P-complete”?
Let $X$ denote a (decision) problem in NP and let #$X$ denote its counting version.
Under what conditions is it known that "X is NP-complete" $\implies$ "#X is #P-complete"?
Of course the existence ...
4
votes
0answers
104 views
What is the complexity of pallet loading for identical non-rectangular objects?
In the pallet loading problem, we are asked to place a set of small identical 2-D rigid objects into a large bounding rectangle such that no two objects overlap. This problem is a special case of the ...
11
votes
3answers
401 views
Does NP-completeness/hardness have to be constructive?
Is there any $L\in {\bf NP}$ with the following properties:
It is known that $L\in {\bf P}$ implies ${\bf P}={\bf NP}$.
There is no (known) polynomial time Turing reduction of $SAT$ (or some other ...
6
votes
1answer
226 views
NP-hardness of an optimization problem
While studying a problem in algorithmic game theory I got interested
in the complexity of the following optimization question:
Problem
Given:
ground set $U = [n] = \{1,\ldots,n\}$ given by $n$,
...
18
votes
1answer
323 views
Is there a problem that is easy for cubic graph but hard for graphs with maximum degree 3?
Cubic graphs are graphs where every vertex has degree 3. They have been extensively studied and I'm aware that several NP-hard problems remain NP-hard even restricted to subclasses of cubic graphs, ...
-3
votes
1answer
93 views
Difference between 'Reductions' in algebraic problems vs “Reductions” in Computational Intractability [closed]
When I read NP-completeness for the first time, I really wondered why is the concept of Reductions given such high emphasis, after all we have been looking at concepts such as reductions and 'special ...
8
votes
1answer
202 views
The complexity of the puzzle game Net
Net (known also as FreeNet, or as NetWalk) is a puzzle game played on a $n \times n$ grid with the following objects:
there are $m$ computers ; each computer occupies one cell and has one link ...
14
votes
2answers
375 views
The motivation for using Karp-reductions in the theory of $\mathcal{NP}$-completeness
The notion of polynomial time reductions (Cook reductions) is an abstraction of a very intuitive concept: efficiently solving a problem by using an algorithm for a different problem.
However, in the ...
21
votes
2answers
659 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. ...
3
votes
1answer
124 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'$ ...
18
votes
4answers
512 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 ...
3
votes
1answer
192 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 ...
13
votes
1answer
186 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 ...
1
vote
1answer
277 views
Guidelines to reduce general TSP to Triangle TSP
I am looking for the method / correct way to approach to reduce the traveling salesman problem to an instance of traveling salesman problem which satisfies the triangle inequality, ie:
$D(a, b) \leq ...
1
vote
1answer
295 views
Vehicle routing problem over Manhattan distances
I am looking for references to the variant of the vehicle routing problem over Manhattan distance metric where the aim is to optimize the number of tours starting at the depot.
Is the following ...
