Questions tagged [np-hard]
decision problems that are at least as hard as NP-complete problems
732
questions
1
vote
0
answers
22
views
Minimize sum of products of partition [closed]
I have a set of positive integer numbers $A = \{a_1,...,a_N\}$ and I need to find a partition of $A$ into two sets, such that the sum of their products is minimal, i.e.,
$$
\min_{X,Y : X \cup Y = A} \...
- 11
2
votes
0
answers
57
views
Exact Cover variant: partition a family of subsets into exact coverings
I have found that a problem that I'm analyzing is equivalent to the following variant of the Exact Cover problem:
Partition into $k$ Exact Covers
Input: A universe ...
- 111
1
vote
1
answer
38
views
If every NP-hard language is PSPACE-hard then NP=PSPACE
To prove PSAPCE = NP we will show following inclusions :
NP $\subseteq$ PSPACE : If every NP-hard language is PSPACE-hard then
SAT is also PSPACE-hard. Since every language in PSPACE can be
reduced ...
- 173
0
votes
2
answers
38
views
Are all np-complete problems also np-hard?
Are all np-complete problems also np-hard?
In other words, is np-complete a subset of np-hard?
I don't think it is entirely clear from the illsutration below, so I just wanted to quickly ask to ask to ...
0
votes
1
answer
30
views
Complexity of the partition problem with additional constraint
The "classical" partition problem asks whether a given multiset $S$ of positive integers can be partitioned into two subsets $S_1$ and $S_2$ such that the sum of the numbers in $S_1$ equals ...
2
votes
2
answers
264
views
The class of problems that can be solved efficiently using physical means?
By "physical means", I mean, for example, using water pouring down tubes, or combining chemicals, etc. Basically, using some experiment in the physical world to perform some computation. I'...
- 409
1
vote
1
answer
54
views
Determining whether formula is only satisfied by the all-true assignment
I'm trying to prove that $\mathrm{HALF}\text-\mathrm{FALSE}$ is NP-hard, where $\mathrm{HALF}\text-\mathrm{FALSE}$ is the following problem:
given a boolean formula $\phi(x_1,\dots,x_n)$, is there a ...
- 11
1
vote
1
answer
79
views
Covering all colors with unit intervals
Suppose we are given $n$ points on the real line, where each point is colored with a color from set $C=\{c_1,c_2,\ldots,c_k\}$ that contains $k$ distinct colors. We try to cover the $k$ distinct ...
- 11
1
vote
1
answer
40
views
Is finding the union of all minimum hitting sets NP-hard?
Let's start with the well-known minimum hitting set problem (known to be NP-hard): given some collection of sets: $U = \{S_1, S_2, S_3\} = \{\{1, 2, 5, 9\}, \{1,2,7\}, \{42, 13, 23, 1, 2\}\}$ for ...
- 13
1
vote
1
answer
172
views
Proof that 2-sat is P-hard?
i figured out this is what i want to know:
in Cook's theorem it is shown that SAT is NP-hard. he shows it by showing that sat is at least as difficult like the word problem for nondet. Polynomial Time ...
- 11
5
votes
2
answers
86
views
Name and complexity of this problem on bipartite graphs
Let $G=(U, V, E)$ be a biparite graph, with $U$ and $V$ being the two sets of nodes.
I am trying to find the smallest set of nodes $\hat{V} \subseteq V$ such that, for every node $u \in U$, $\hat{V}_u$...
9
votes
1
answer
2k
views
Why rectangle packing is NP-hard but maybe not in NP?
Recently I studied a MIT open course.
In lecture2, it is stated that Rectangle Packing is NP-hard.
I can understand this because the problem can be reduced to 3-partition problem
But I don't know why ...
- 153
0
votes
1
answer
27
views
Knapsack with quadratic constraint
Suppose I have a variant of the knapsack problem:
$$\max_{x} \sum_{i=1}^n v_ix_i$$
$$(\sum_{i=1}^n w_ix_i - W)^2 \leq k$$
for $v_i, w_i \in \mathbb{R}$, $x_i \in \{0,1\}$ and $k \in \mathbb{R}, k > ...
2
votes
1
answer
57
views
NP-completeness of some problems on assigning candidates to departments
Suppose we have $n$ candidates from a candidate pool $\{1,2, .., n\}$ and we have $m$ departments. A candidate can be assigned to at most one department (so not being assigned is possible). Each ...
- 21
-1
votes
1
answer
34
views
What kind of problems in the world can be classified into PSPACE categories?
For instance can we categorize the following problems into NP-Hard ?
Is the Universe finite ?
Is there life after death ?
What came first, the chicken or the egg ?
My question is more around what ...
- 99
1
vote
1
answer
48
views
Proving the NP hardness of two variants of SAT
$k$-$\text{RSAT}$ is a variant of $k$-$\text{SAT}$ where we restrict our attention to formulae in
which each variable occurs at most $3$ times, and each literal occurs at most twice. The language
$k$-$...
- 369
3
votes
1
answer
101
views
4-SAT but two literals per clause must be true
I'm trying to show that a modified 4-SAT in which at least two literals per clause must be true is NP-complete. I'll call it $4_2$-SAT. I understand the reduction from 3-SAT to 4-SAT, and I know why $...
- 31
1
vote
1
answer
42
views
Find a perfect matching with weights as close as possible to each other
Given a set of jobs $J$ and a set of machines $M$, where the link between machine $i\in M$ and job $j\in J$ has a positive weight $w_{ij}$. The problem is to select a perfect matching between the jobs ...
- 1,016
2
votes
1
answer
48
views
Reduction from vertex-cover to system of quadratic equations
Define
$$\text{SQE}=\{S\ |\ S\ \text{is a system of quadratic equations with real solutions}\}$$
and
$$\text{VC}=\{G\ |\ G\ \text{is a simple undirected graph with a vertex cover}\ \leq k\}$$
I am ...
- 248
0
votes
1
answer
43
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?
- 3
0
votes
0
answers
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 ...
- 13
2
votes
1
answer
47
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 ...
- 21
1
vote
1
answer
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 ...
- 13
1
vote
0
answers
23
views
Assumptions needed by Exact Cover by 3-Sets (X3C)
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_{...
- 65
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
66
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 ...
- 69
3
votes
0
answers
58
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 ...
- 31
2
votes
2
answers
902
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$, ...
- 123
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 ...
- 1
0
votes
1
answer
25
views
MAX-LP: maximize number of linear inequalities satisfied
Consider the following variant of linear programming, where we want to maximize the number of linear inequalities that are satisfied:
Input: linear inequalities $A_1x\le b_1$, ..., $A_nx \le b_n$; an ...
D.W.♦
- 141k
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'| ...
- 215
9
votes
1
answer
602
views
Spatial embedding of graph
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 ...
- 215
1
vote
1
answer
47
views
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 ...
- 131
1
vote
0
answers
22
views
Best known approximation for P2|tree;pj=1;Mj|Cmax
I am looking for the best known approximation algorithm for the scheduling problem $P2|tree;p_j=1;M_j|C_{max}$, which to my knowledge is at least $\mathbb{NP}$-hard.
A more elaborate description of ...
- 11
3
votes
1
answer
57
views
variant of assignment problem with overload penalties instead of constraints
I want to assign $m$ tasks to $n$ workers where $m>n$, so as to minimize assignment costs defined by an $m \times n$ matrix $C$. That is, I want to find Boolean variables $x_{i,j}$ which minimize
$$...
- 78
0
votes
1
answer
34
views
Subclass of problems of an NP hard problem
I have an NP hard problem $P$ that takes in arbitrary $G = (V, E)$ as input. I have another problem $Q$ that I want to show is NP hard, and this problem has arbitrary complete graphs $G'$ as input. Is ...
- 151
1
vote
1
answer
73
views
Why NP-Complete reduction is not reversible?
I have read the question asked here Is polynomial reduction reversible and the logic actually makes sense to me. In other words, if A is polynomially reducible to B, it means that A <= B in terms ...
- 65
2
votes
1
answer
21
views
How we transform IS inputs to VC (reduction)?
I would like to clarify something in my understanding of proving a problem to be NP-hard.
So in short, what I know is that:
"If I have a problem A that I want to prove that is NP-hard and another ...
- 201
-1
votes
1
answer
80
views
if P=NP, and if language A is not NP-hard, A = ∅ or A = Σ*
I don't know how to solve this.
Show that if P=NP, and if language A is not NP-hard, A = ∅ or A = Σ*
- 7
2
votes
1
answer
73
views
Maximum independent subset for graphs with lots of edges
Consider an NP-hard graph problem, like the maximum independent set problem.
Let us say I restrict my inputs to only be graphs that have $n$ vertices and at least $n^{c}$ edges, for some $c > 1$. ...
- 309
0
votes
1
answer
62
views
How can i do this type of swap(4-opt) between 4 edges of a graph?
The double bridge move is a specific type of swap between 4 edges of a graph, also called 4-opt. It consists of removing 2 pairs of edges. Let`s call them (I, I+1), (J, J+1) and (P, P+1), (Q, Q+1). ...
3
votes
1
answer
66
views
Can it be NP hard to calculate the value of a function?
So, I've just begun dabbling in complexity theory and I'm somewhat confused as to the relationship between NP-hardness and function computation. As far as I've understood, NP-hardness is defined for ...
- 31
0
votes
0
answers
24
views
Reduction from SAT to EXACTSAT
PROBLEM: EXACTSAT
INPUT: A boolean formula $\phi$ in CNF with $n$ variables, and a natural number $k \le n$.
OUTPUT: "Yes" if and only if there is truth assignment $\theta$ which sets ...
1
vote
1
answer
42
views
Fastest way to find optimal graph coloring in polynomial space given chromatic number
Suppose I have a graph's chromatic number. Give a faster-than-brute-force polynomial-space algorithm for finding an optimal coloring.
If such an algorithm isn't known, please tell me so.
This question ...
- 83
0
votes
2
answers
91
views
Can we DISPROVE that a problem is NP-complete
So I basically had an exam question in which we were given a problem and we had to prove or disprove that it was in NP-complete. I tried to prove it but could not because apparently it could not be ...
- 1
1
vote
1
answer
41
views
Where does each part of the $1 - (1 - 1/k)^k$ approximation for the Maximum Coverage problem come from?
A solution to an instance of the Maximum Coverage problem with a budget of k subsets can be approximated with a greedy algorithm that, at each iteration, picks one of the subsets that adds the most ...
-2
votes
2
answers
159
views
If the halting problem is NP hard, would P = NP with a hypercomputer capable of computing the halting problem in polynomial time?
The halting problem is NP hard, to my knowledge any NP problem can be reduced to a NP hard problem. Let us define a new computational complexity class called HP(Hypercomputational polynomal-time), The ...
- 99
1
vote
1
answer
38
views
A be an NP-complete problem, and if B be an NP-hard problem. If A is polynomial time solvable then is B is polynomial time solvable?
if A be an NP-complete problem, and if B be an NP-hard problem. If A is polynomial
time solvable then is B is polynomial time solvable?
on the contrary, if A be an NP-complete problem, and B be an NP-...
- 11
-1
votes
1
answer
44
views
Prove that T3SAT is NP-Complete
Instance: A boolean formula f(x1, . . . , xn) in 3CNF form, with m clauses labelled C1, . . . , Cm.
Is there an assignment to x1, . . . , xn such that every third clause is False and all other clauses ...
- 11
0
votes
1
answer
44
views
Is integer multicommodity flow problem is NP-hard?
As Wikipedia states the time complexity of Integer Linear programming(ILP) is NP-hard, so this means integer multicommodity flow problem is also NP-hard?
- 1