Questions tagged [np-hard]
decision problems that are at least as hard as NP-complete problems
-1
votes
1answer
35 views
i-max-clique is np complete
How to prove the np completeness of the problem i-max-clique ?
iMC is defined as follows:
Given "i" number of cliques and "k" size of the clique, the graph will contain 'i' cliques at size 'k'
1
vote
1answer
22 views
Reducing 3 SAT to 3 SET PACKING
I'm trying to prove NP-hardness of 3 SET PACKING, which is a following problem: given a family of sets where each set contains 3 elements, decide whether the family contains k sets that are pairwise ...
2
votes
2answers
51 views
Prove that this language is NP-Hard
Given
$$\mathrm{\#3SAT} = \{ (w, y) \mid w\text{ is a $\mathrm{3SAT}$ instance with at least $y$ satisfying assignments}\}\,,$$
prove that $\mathrm{\#3SAT}$ is NP-Hard.
I am currently stuck with ...
0
votes
1answer
115 views
Proving NP completeness of maximal length path
I have this question to answer:
For each node i in an undirected network $G = (N,E)$, let $N(i) = \{j \in N : \{i, j\} \in E\}$ denote the set of neighbors of node $i$ and let $c_e\geq0$ denote the ...
0
votes
1answer
38 views
Time complexity of subset sum problem with reals instead?
It is well known that the conventional subset sum problem with integers is NP-complete. What if the array elements can be any real numbers and also target sum can be any real number? Is it NP-complete ...
3
votes
1answer
33 views
Quantum vs classic in NP-hard problems
Is there any quantum algorithm (algorithm for quantum computers) for any NP-hard problem that has better runtime than the best known classic algorithm's runtime?
-1
votes
1answer
29 views
If a problem C is NP hard and there is an existing reduction from/to A,B,D, are they NP hard as well?
Lets say there is an reduction in polynomial time from problem A to B, from problem B to C and from problem C to D. Now lets say C is NP hard. Does this mean A,B,D are NP hard as well?
2
votes
1answer
44 views
Existence of path under weight and value budgets
Consider the following problem:
Input: An undirected graph $G = (V, E)$, each edge has a non-negative weight $w_i$ and a non-negative value $v_i$. There are two vertices to represent start point $s$...
2
votes
1answer
54 views
The Ising Model and Computational Complexity
I've been told recently that one can use the Ising model can find solutions to certain NP-hard problems, such as Clique, although it doesn't do so in polynomial time.
Googling gets a few Arxiv ...
5
votes
1answer
78 views
Reduction from Exact Cover to Fixed Exact Cover
I am trying to reduce Exact Cover to Fixed Exact Cover to show that Fixed Exact Cover is NP-Hard.
Exact Cover
Input
S = {x1, x2, ..., xn} (set)
P = {P1, P2, ..., Pm} (subsets of S)
Decision ...
0
votes
1answer
32 views
What are the current state of art approximation algorithm for NP-Hard problems? [closed]
I came cross some works try to use deep learning to approximate NP-Hard
https://arxiv.org/pdf/1810.10659.pdf
Though the paper seems to have very good results but based on the citations. I'm quit ...
0
votes
1answer
68 views
Subset with modified condition, is it still NP-complete? [closed]
So I know the conditions required for a problem to be NP-Complete is that it has to lie within NP and has to be NP-hard.
The given problem I have is subset sum.
However, the conditions have been ...
1
vote
2answers
93 views
Reduce 4-SAT to 5-SAT
given is a reduction from 4-SAT to 5-SAT.
How is it possible to describe such a function?
I found some informations about reduction 3-SAT to 4-SAT here, but it can't help me so much.
0
votes
0answers
26 views
Is retrospective inference NP-hard?
Here is a minimal working example of the question:
Consider a network with nodes arranged in a pyramid: $1$ node in the first row, $1+d$ nodes in the second, $1+2d$ nodes in the third, and so on, ...
2
votes
0answers
40 views
Is a “stacked”, “local” version of 3-SAT NP-hard?
In this previous question, I learned that if each variable in a string $C \in 3\text{-SAT}$ appears only "locally", then finding a satisfying assignment is no longer NP-hard. My question below builds ...
0
votes
0answers
34 views
Job scheduling with minimum makespan
You are given n jobs, m workstations and an n × m two-dimensional task matrix T of the time each job will spend at each workstation. Each job becomes available at a specified time and may be processed ...
7
votes
1answer
398 views
Is a “local” version of 3-SAT NP-hard?
Below is my simplification of part of a larger research project on spatial Bayesian networks:
Say a variable is "$k$-local" in a string $C \in 3\text{-CNF}$ if there are fewer than $k$ clauses ...
7
votes
1answer
1k views
Is this possible when it comes to the relations of P, NP, NP-Hard and NP-Complete?
I saw an image that describes the relations of P, NP, NP-Hard and NP-Complete which look like this :
https://en.wikipedia.org/wiki/NP-hardness#/media/File:P_np_np-complete_np-hard.svg
I wonder if ...
1
vote
1answer
82 views
P vs NP question from GeeksforGeeks
From here: https://www.geeksforgeeks.org/algorithms-np-complete-question-2/
Let S be an NP-complete problem and Q and R be two other problems not known to be in NP. Q is polynomial time reducible to ...
1
vote
2answers
48 views
Maximal cliques in a multipartite graph - efficient?
I am looking at a combinatorial optimisation problem where I have N classes and k objects of each class.
Now I am looking for the optimal subset such that each of the N classes is represented ...
2
votes
1answer
40 views
Decision variation of max sat
I am trying to prove that following decison variation of MaxSAT is both NP hard and co-NP hard.
$(\phi ,k) \in L$ iff an assignment of $\phi$ satisfies k clauses and no assignment satisfies more than ...
0
votes
1answer
45 views
MILP problem NP-hard proof [closed]
Since a MILP problem is not necessarily NP hard. How could I demonstrate that a MILP problem is actually NP hard? There exists some smart and easy method to do that?
Many thanks!
0
votes
1answer
33 views
Can a NP problem be reduced to another NP problem?
I have three related questions which have been bothering me for a while now...
Suppose I have a problem $A$, which is in NP. Suppose there is another
problem $B$ in NP, can I ...
8
votes
2answers
2k views
Is “Reachable Object” really an NP-complete problem?
I was reading this paper where the authors explain Theorem 1, which states "Reachable Object" (as defined in the paper) is NP-complete. However, they prove the reduction only in one direction, i.e. ...
0
votes
1answer
48 views
How can I develop a pseudo-polynomial time algorithm for a non-integer problem?
I have an scheduling probelm with a set of jobs $J$, with a ''non-integer'' parameter $\beta_j$, i.e. the parameter is a real number and $\beta_j \leqslant 0.5, \exists j \in J$.
Since the problem ...
1
vote
0answers
42 views
Delivering to two or more locations in one go while respecting deadlines?
Assume that I have a business where people can place product orders. Each order must be delivered within a time limit, say $x$ minutes.
I need 15 minutes to make each product. However, multiple ...
3
votes
1answer
50 views
Clarification on NP-hardness and hardness of approximation results for set cover?
I'm not familiar with complexity theory at all so please correct me if I make any incorrect statements.
I am wondering what is the hard case of set cover? My understanding of NP-hardness is that it ...
0
votes
0answers
22 views
Finding “good” order of elements for the purpose of material minimization
I am working with metallic shapes which are curved and highly irregular. The initial order of them is random and by default they are merely sorted by size, which is simple. However the resulting order ...
0
votes
0answers
54 views
Implementing a job-scheduling problem with multiple dependencies and variable tasks (time frames) using dynamic programming
I'm writing a "Chores Scheduler" in Python. It has to be implemented using dynamic programming and has to take in two types of chores, as below:
Regular chores with a start time and end time (a real-...
0
votes
0answers
25 views
Where f(n) = n! belongs to? P, co-P, NPComplete or NPHard? [duplicate]
Where f(n) = n! belongs to? P, co-P, NPComplete or NPHard?
4
votes
0answers
104 views
Is Hamiltonian cycle problem on graphs with out-degree at most 3 NP hard?
I am trying to show a different form of Hamiltonian cycle problem is NP Hard. The problem is as follows.
We have a directed graph and each node can have at most 3 outgoing edges. Determine if this ...
0
votes
1answer
110 views
Turing Machine that both halts and loops in NP
This is in regards to a specific TM:
$UNIQUE: \{$ TM | TM loops on at least an input, and TM also halts on at least one input $\}$
This is a play on the Halting Problem, where it basically combines $...
2
votes
1answer
58 views
How to partition a set in order to minimize the number of the elements and their interactions?
Given two sets $S_1$ and $S_2$ of $n$ elements each. Each set $S_1$ (resp. $S_2$) has a revenue $R_1$ (resp. $R_2$). Each element $i$ of $S_1$ (resp. $S_2$) has a gain $g_{i1}$ (resp. $g_{i2}$). From ...
3
votes
0answers
82 views
A special case of the SUBSET SUM problem
Consider the following special case of SUBSET SUM
Inputs: Positive integers $a$ and $b$ with $a \ne b$, and positive integers $k$ and $t$, with $k$ specified in unary.
Encoding: These inputs (...
1
vote
0answers
22 views
Given a subset of numbers $1, \dots, n$, find the minimal subset of numbers $1, \dots, n$ sums of every subset of which cover all sums of first subset
Given a subset $A = \{a_1, a_2, \dots, a_k\}$ of numbers $\{1, 2, \dots, n\}$, find another subset $B = \{b_1, b_2, \dots, b_t\}$ of numbers $\{1, 2, \dots, n\}$ of minimal size (that is, minimise $t$)...
2
votes
1answer
79 views
Reducing the vertex cover problem to a variation of the vertex cover problem [duplicate]
The following variation on the vertex cover problem was given:
Given is an instance of graph $G = (V, E)$. Does $G$ have a vertex cover of size at most $\frac{|V|}{4}$?
I was asked to prove that ...
1
vote
1answer
90 views
Is there a polynomial-time reduction from a NP-hard problem to the complement of tautology?
Is the following true or false? Why?
Let $Y$ denote the complement of the tautology problem. If a problem X is NP-hard, then there is a polynomial-time (many-one) reduction of $Y \leq_{p} X$.
2
votes
1answer
293 views
Reducing 3SAT to a Set Splitting Problem
I want to be able to reduce the 3SAT problem to a flavor of set-splitting problem. Basically, given $n$ items and $m$ subsets $S_1, S_2,...,S_m$ of these items I want a yes or no answer based upon the ...
3
votes
1answer
35 views
How to generate snowflakes of a fixed area as challenges for the FridgeIQ puzzle?
I have been presented a set of FridgeIQ by a friend and she has planted an idea in my head.
FridgeIQ is a geometric disection puzzle consisting of 16 polygonal tiles as seen in the terrible picture ...
2
votes
2answers
232 views
Negative simple path NP-Complete
Given a graph $G=(V,E)$, and positive and negative edge weights, negative path problem asks if there is a simple path with negative total weight from $s$ to $t$ where $s,t \in V$
My approach was to ...
0
votes
1answer
30 views
Is this problem hard? Finding all the subsets of size k from a sequence of n numbers
I want to know the hardness of finding all subsets of size k from a sequence of n numbers. There is an algorithm based on recursion: Print all possible combinations of r elements in a given array of ...
0
votes
1answer
106 views
Showing party invitation problem is np-complete
Suppose you and your $k - 1$ housemates decide to throw a party. Each housemate $i$ gives you a list $P_i$ of people she would like to have invited to the party. Depending on how much you like ...
1
vote
1answer
58 views
Show Resource Allocation Problem is NP-Complete
We are given $n$ tasks and $m$ resources. Each task $i$ requires a set $S_i$ of resources to be active, and each resource can be used by at most one task. The Resource Allocation problem asks: given $...
1
vote
1answer
37 views
Finding a suitable NP-complete problem for reduction
We are given a set of names and a set of papers with names written on each side of the paper (not necessarily different ones and either side of the paper can be empty). Can we place the sheets on a ...
1
vote
1answer
70 views
Why Cook-Levin thorem's proof can mean SAT's NP-Hardness
I'm studying about Cook-Levin theorem but there is a problem I faced. Cook-Levin theorem shows that any NPTM can be encoded as a boolean formula. About given language $A$, instance $w$, and NPTM $M$ ...
0
votes
0answers
36 views
Why finding out an independent set of size k is in NP-C and not in P? [duplicate]
I came across a statement in my book which claims that the problem P1 in NP-C and P2 is P.
P1: Given graph G(V, E), find out whether there exists an independent set of size k in the graph, where k is ...
1
vote
2answers
32 views
NP-hardness does not imply lower bound, strictly speaking?
A problem is NP-hard iff every NP problem can be polynomially-time reduced to it.
Hardness is often intuitively explained as a lower bound. But it isn't, strictly ...
3
votes
1answer
52 views
Proving NP hardness about graph creation problem with triangle number
I have graph creation problem.
Given a set of nodes of graph, and node constraints such as given every node's number of neighbors (degree). I am also provided with the total number of triangles in ...
2
votes
1answer
81 views
Max flow and Matching problem
Where can i find a list of problems reducible to max flow and matching problems. I need such examples to learn and practice .
2
votes
0answers
26 views
Karp hardness of two vertex sets in a digraph
Given a digraph $G(V,A)$ and a number $k$, we want to find two vertex subsets $S,T\subseteq V$ such that:
$|S|+|T|=k$
For every $v\notin S\cup T$, $v$ has no arcs coming to $S$, and no arcs coming ...
