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 ...