decision problems that are at least as hard as NP-complete problems
2
votes
0answers
10 views
Hardness of a special case of maximum matching
Input: A set of $n$ Users $U=\{u_1, ..., u_n\}$ and a set of $m$ products $I=\{i_1, ..., i_m\}$. Associated with each pair $u \in U$ and $i \in I$ is the probability $p_{u,i}$ of $u$ purchasing ...
1
vote
1answer
57 views
Hardness of approximation of the 3 colorability problem
If we have polynomial algorithm that $c$-approximation, $c<\frac{4}{3}$ for graphs that their chromatic number $\geq k$ then $NP=P$, how to prove such statements?
I also have some sort of ...
2
votes
1answer
46 views
Generating 3SAT circuit for Integer factorization example
I read somewhere that 3SAT can be used to solve Integer Factorization.
If that is true, could someone teach me a simple example of generating the 3SAT by using a small number? Let's say you are given ...
0
votes
1answer
42 views
Show that this language is in NP $\cap$ coNP
Say $\ell: \{0,1\}^\ast \to \{0,1\}^\ast$ is a one-to-one polynomial-time computable function that preserves length. Consider the language $$L = \Bigl\{v \;\Big|\; \exists u: \bigl(u_1 = 1 ...
3
votes
0answers
41 views
Decision vs Optimization version for Problems of two Parameters
Let's say I have an optimization problem called $k$-foo which asks for a solution of size $k$ minimizing some quality criterion.
Now the corresponding decision problem $foo(M)$ would be: Is there a ...
4
votes
1answer
61 views
NP hardness through Restriction
Let's say I have a decision problem $P$ on graphs for which I know that it is NP-hard on graphs with maximum degree $d$. Does this then imply that it is NP-hard on $d$-regular graphs? Although it ...
-1
votes
0answers
31 views
In a directed graph, the indegree of a node is the number of incoming edges and the outdegree is the number of outgoing edges [duplicate]
In a directed graph, the indegree of a node is the number of incoming edges and
the outdegree is the number of outgoing edges. Show that the following problem
is NP-complete. Given an undirected graph ...
1
vote
2answers
97 views
Show that the following problem is NP-complete
In a directed graph, the indegree of a node is the number of incoming edges and
the outdegree is the number of outgoing edges. Show that the following problem
is NP-complete. Given an undirected graph ...
10
votes
2answers
147 views
Is Hidoku NP complete?
A Hidoku is a $n \times n$ grid with some pre-filled integers from 1 to $n^2$. The goal is to find a path of successive integers (from 1 to $n^2$) in the grid. More concrete, each cell of the grid ...
3
votes
1answer
31 views
Minimizing a multivariate polynomial over the hyper-cube is NP-Hard
In an exercise I have to show that minimizing a multivariate polynomial with $n$ variables over the hyper-cube $H = \{ (x_1, \ldots, x_n) : 0 \leq x_i \leq 1 \}$ is NP-Hard. Formally, given $p(x_1, ...
3
votes
1answer
144 views
Do any decision problems exist outside NP and NP-Hard?
This question asks about NP-hard problems that are not NP-complete. I'm wondering if there exist any decision problems that are neither NP nor NP-hard.
In order to be in NP, problems have to have a ...
5
votes
1answer
71 views
Subset Sum: reduce special to general case
Wikipedia states the subset sum problem as finding a subset of a given set of integers, whose sum is zero. Further it describes it as equivalent to finding a subset with sum $s$ for any given $s$.
So ...
0
votes
2answers
69 views
How to reduce from subset-sum problem?
I have this problem which is described as follows:
Input:
You are given a multi-set $M$ (a set that can contain duplicates), and two numbers $P$ and $T$.
$M = {(x_1,y_1), (x_2,y_2), ..., ...
0
votes
1answer
79 views
0
votes
0answers
27 views
1
vote
3answers
60 views
Does hardness of a special case imply hardness of a general case?
I am wondering in general if it is correct to claim that if a special case of a problem is NP-Hard, the general case of that problem is NP-
Hard too?
For example: Min Set-Cover is NP-Hard does it ...
2
votes
0answers
39 views
Travelling salesman problem with detours
I am interested if there exists a following version of the travelling salesman problem:
INSTANCE: A finite set $C = \{1,2,\dots,k\}$ of cities, a positive integer distance $\delta(i,j)$ for each ...
12
votes
2answers
294 views
NP-Hard that is not NP-Complete and not Undecidable
I'm wondering if there is a good example for an easy to understand NP-Hard problem that is not NP-Complete and not undecidable?
For example, the halting problem is NP-Hard, not NP-Complete, but is ...
3
votes
3answers
209 views
Finding all solutions to subset sum for integers with bounded weights
Suppose I have the set of weights $W = \{w_1,w_2,\ldots,w_{50}\}$ where each $1 \le w_i \le 60$ is an integer. I am interested in determining all subsets (not just one, and not just the number of ...
5
votes
1answer
97 views
For what special cases does this vertex cover algorithm fail or work?
I'm trying to find a polynomial time algorithm for finding the minimum vertex cover for a graph. I've written the algorithm below; I know this problem is $\mathsf{NP}$-hard, which means there are ...
3
votes
1answer
95 views
Circuit Satisfiability problem is NP-Hard?
$\newcommand{\np}{\mathsf{NP}}\newcommand{\cc}{\textrm{Circuit-SAT}}$I am having difficulty understanding the $\np$-hardness proof for $\cc$ in CLRS.
$\cc = \{\langle C \rangle : C \text{ is a ...
4
votes
1answer
114 views
NP-Hard problems which are not NP-Complete
Is it always true that a problem which is ${\sf NP}$-hard but not ${\sf NP}$-complete is an optimization problem such as Minimum-Vertex-Cover and many others.
Is it always true that a ${\sf ...
2
votes
3answers
73 views
Difference between reductions in algebraic problems versus reductions in computational intractability
When I read about 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 ...
5
votes
1answer
127 views
Does Max-SNP hard imply NP-hard
I have difficulties understanding the definition of the class Max-SNP (optimization variant of strict NP), thus I have to following basic question:
...
7
votes
2answers
137 views
Reduce the following problem to SAT
Here is the problem. Given $k, n, T_1, \ldots, T_m$, where each $T_i \subseteq \{1, \ldots, n\}$. Is there a subset $S \subseteq \{1, \ldots, n\}$ with size at most $k$ such that $S \cap T_i \neq ...
2
votes
1answer
163 views
Modification of Hamilton Path
Although I know that the Hamilton Path problem is ${\sf NP}$-complete, I think the following variant can be solved in polynomial time:
Given a planar graph with vertex set $V$, edge set $E$, start ...
4
votes
3answers
413 views
What is the relationship between NP/NP-Complete/NP-Hard to time complexity?
I'm familiar with a few problems of each class and even though the definitions are based on sets and polynomial reducibility, I see a pattern with time complexity. NP problems appear to be $O(2^n)$ ...
2
votes
0answers
99 views
Reduction from knapsack problem to Integer relation that equals one
My question is related to the Integer Relation Detection Problem which can be formulated as:
$\qquad a_1x_1 + a_2x_2 + \cdots + a_nx_n = 0$
Where $\forall i. a_i\in\mathbb{Z} \land a_i<c \land ...
3
votes
2answers
205 views
How to reduce to an NP-hard problem?
For an assignment I have to program an application to schedule conversations.
There is an event where representatives of the elementary schools talks with the representatives of high schools. They ...
7
votes
1answer
112 views
Find small superset of at least k of n given sets
Say we're given $n$ sets and the size of their union is $m$. We would like to construct a small set which contains at least $k$ of the $n$ given sets.
Lets assume that $m$ is less than some ...
4
votes
0answers
80 views
Find a permutation that maximize the minimum of $\frac{a_n}{a_{n-1}} + \frac{a_n}{a_{n+1}}$
Consider a sequence of $n$ positive real numbers $a_0,\ldots,a_{n-1}$. Let $S_n$ be the set of permutations on $\{0,\ldots,n-1\}$.
We are interested to find
$$
\max_{\pi\in S_n}\left( ...
4
votes
1answer
151 views
What complexity class does this variation of traveling salesman problem belong to?
Given a TSP instance $T$, decide whether changing the city coordinates by adding a vector of coordinates $v$ will change the optimal TSP objective by atleast $x$. The city coordinates are integers.
...
3
votes
1answer
99 views
The $\text{k-key}$ problem
Given an undirected graph, I define a structure called k-key as a path containing $k$ vertices which are connected to a simple cycle which contains $k$ vertices as well.
Here's the k-key problem: ...
2
votes
1answer
201 views
NP-completeness of graph isomorphism through edge contractions with an edge validity condition
Given Graphs $G=(V_1,E_1)$ and $H=(V_2,E_2)$. Can a graph isomorphic to $H$ be obtained from $G$ by a sequence of edge contractions ? We know this problem is NP-complete. What about if only a subset ...
3
votes
1answer
109 views
Is NP-hard closed against cartesian product with arbitrary languages?
If $L_1$ is NP-hard, $L_1 \times L_2$ is NP-hard for every $L_2 \neq \emptyset$, where
$\qquad \displaystyle L_1 \times L_2 = \{(w_1,w_2) \mid w_1 \in L_1, w_2 \in L_2\}$
Is it true or false and ...
-1
votes
1answer
153 views
Solve a problem through reduction
I am aware that for a problem to be considered NP-Hard, any problem in NP must be reduceable to your problem (problem which you are trying to prove is NP-Hard).
Let's assume that you have proven that ...
9
votes
3answers
251 views
Is connecting islands with pontoons NP-complete?
I have a problem in my mind, I think it is a NPC problem but I don't know how to prove it.
Here is the problem:
There are k islands in a very big lake, and there are n fan-shaped pontoons. Those ...
8
votes
1answer
222 views
A continuous optimization problem that reduces to TSP
Suppose I am given a finite set of points $p_1,p_2,..p_n$ in the plane, and asked to draw a twice-differentiable curve $C(P)$ through the $p_i$'s, such that its perimeter is as small as possible. ...
7
votes
1answer
215 views
Proving that directed graph diagnosis is NP-hard
I have a homework assignment that I've been bashing my head against for some time, and I'd appreciate any hints. It is about choosing a known problem, the NP-completeness of which is proven, and ...
5
votes
1answer
206 views
Reduction to equipartition problem from the partition problem?
Equipartition Problem:
Instance: $2n$ positive integers $x_1,\dots,x_{2n}$ such that their sum is even. Let $B$ denote half their sum, so that $\sum x_{i} = 2B$.
Query: Is there a subset $I ...
18
votes
2answers
446 views
Decision problems vs “real” problems that aren't yes-or-no
I read in many places that some problems are difficult to approximate (it is NP-hard to approximate them). But approximation is not a decision problem: the answer is a real number and not Yes or No. ...
36
votes
4answers
1k views
Why hasn't there been an encryption algorithm that is based on the known NP-Hard problems?
Most of today's encryption, such as the RSA, relies on the integer factorization, which is not believed to be a NP-hard problem, but it belongs to BQP, which makes it vulnerable to quantum computers. ...
14
votes
1answer
848 views
Easy reduction from 3SAT to Hamiltonian path problem
There is a reduction in Sipser's book "Introduction to the theory of computation" on page 286 from 3SAT to Hamiltonian path problem.
Is there a simpler reduction?
By simpler I mean a reduction ...
16
votes
1answer
782 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 ...
6
votes
1answer
182 views
CNF to DNF — conversion is NP Hard
How can i prove that the conversion from CNF to DNF is NP-Hard. I'm not asking for an answer, just some suggestions about how to go about proving it.
