Questions tagged [np-hard]

decision problems that are at least as hard as NP-complete problems

Filter by
Sorted by
Tagged with
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} \...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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'...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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$...
user avatar
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 ...
user avatar
  • 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 > ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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$-$...
user avatar
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 $...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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?
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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_{...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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$, ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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'| ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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 $$...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
-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 = Σ*
user avatar
  • 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$. ...
user avatar
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). ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
-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 ...
user avatar
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-...
user avatar
  • 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 ...
user avatar
  • 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?
user avatar

1
2 3 4 5
15