Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [np-complete]

Questions about the hardest problems in NP, i.e. of those that can be solved in polynomial time by nondeterministic Turing machines.

0
votes
0answers
6 views

Intuitively, my problem is a mix of perfect hashing, tree spanning, combinatorial stuff - Ordered Decision Tree?

The problem I'm trying to solve is difficult to to give a single name, but I'll call it the ordered decision tree problem. Imagine a row of commands: ...
0
votes
0answers
33 views

Why finding out an independent set of size k is in NP-C and not in P?

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 ...
2
votes
1answer
27 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 ...
1
vote
0answers
20 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 ...
0
votes
3answers
62 views

Which of the following problems can be reduced to the Hamiltonian path problem?

I'm taking the Algorithms: Design and Analysis II class, one of the questions asks: Assume that P ≠ NP. Consider undirected graphs with nonnegative edge lengths. Which of the following problems ...
0
votes
2answers
74 views

Which of the following statements are true for the given special cases of the Traveling Salesman Problem?

I'm taking the Algorithms: Design and Analysis II class, one of the questions asks: Which of the following statements is true? Consider a TSP instance in which every edge cost is either 1 ...
-1
votes
0answers
7 views

How Polynomial-time function is precisely the class of polynomial reductions, which are used in turn to define the class of NP-complete problems?

Polynomial-time function problems are fundamental in defining polynomial-time reductions, which are used in turn to define the class of NP-complete problems. This question was asked in my assignment, ...
1
vote
1answer
30 views

Why any problem can be reduced to SAT is NP-Complete?

I have a book statement says the title, I don't understand it. From my current understanding if a problem A can be reduced to a problem B then it only means B is at least as difficult as A.
3
votes
1answer
422 views

So if a problem is more difficult the language it represents is smaller?

I'm reading the definition of polynomial time reducible: Let $L_1, L_2$ be two language. If $L_1$ is polynomial time reducible to $L_2$ then exists $f:\{0,1\}^*$ s.t. $\forall x\in\{0,1\}^*$ $$x\in ...
0
votes
0answers
20 views

Reduction from IntegerPartition to Knapsack

I had read https://s2.smu.edu/~olinick/emis8373/lectures/complexity/reductions1.pdf Knapsack's np-completeness proof
1
vote
0answers
22 views

Testing if a 4-regular graph can be decomposed into two edge-disjoint Hamiltonian cycles

Given a 4-regular graph, is it NP-complete to test whether it can be decomposed into two edge-disjoint Hamiltonian cycles?
0
votes
1answer
25 views

Complexity of an instance of a NP-complete problem

I am trying to prove the NP-Completeness of problem [A]. I know there is a well-known NP-Complete problem called problem [B]. I can model [A] into an instance of [B] ([B] is a very general problem ...
2
votes
1answer
21 views

Given a set of intervals on the real line, find a minimum set of points that “cover” all the intervals

I've been trying to find an efficient way to solve the problem of finding a minimum (not minimal) set of time points that cover a given family of intervals on the real line, that is, for each interval ...
1
vote
1answer
29 views

Are physical laws uncomputable in any type of computation (according to this article)?

It seems that this article (https://arxiv.org/pdf/1312.4456.pdf) proposes that laws of physics are uncomputable (i.e., they could not be reproduced on a computer), but I'm not sure about it. In some ...
-1
votes
0answers
47 views

Is 3-SAT strongly NP-complete

Can we consider 3-SAT to be strongly NP-complete? In the knapsack problem, we have a polynomial time algorithm in input size when we consider unary encoding of the input. This makes it weakly NP-...
2
votes
1answer
20 views

Resource Reservation: No Greedy Approach?

I'm considering the general resource reservation problem: n processes, m resources. Each process requests a set of resources and each resource can be used by exactly one process. Processes are only ...
1
vote
1answer
120 views

How to reduce 3-COLOR to 42-COLOR?

The requirement is that two adjacent vertices have different colors, and max. 42 colors. I show that $ \text{42-COLOR} $ is in NP and then I must reduce it from $ \text{3-COLOR} $. Here it becomes ...
1
vote
1answer
27 views

Number of divisors of a number - in NP?

I'm trying to show that the language {(m,n)|m has exactly n divisors} is in NP. The input (m,n) is in binary. The non-deterministic Turing machine for the language would be: 1) Guess the prime ...
1
vote
1answer
24 views

Determine whether a system of $n$ linear equations has solutions in $\{0, 1\}^n$ in polynomial time

I'm trying to determine whether it is possible to decide if a system of $n$ linear equations with integer coefficients and $n$ variables has a solution in $\{0, 1\}^n$ in polynomial time. ...
0
votes
1answer
23 views

n-DNF boolean formula k satisfiability

Given an n variable boolean DNF formula and a number k, does this formula has satisfying input combination greater than k?. (0<=k<=2^n). Where input is infinite number of n tuples where ...
1
vote
1answer
35 views

Reducing Independent Set to a problem to prove that it is NP complete

Given: A set of available customers $c_1, c_2, \dots, c_n$. A set of available foods $f_1, f_2, \dots, f_m$. Each customer will choose a subset of the available food. Problem: Find the maximum ...
1
vote
0answers
58 views

Proof of NP Completeness of set-partition problem

I have reduced subset sum problem to set partition problem but do not know whether it is correct and so I need your help. MY METHOD: In subset sum problem we have to find a subset S1 of set S so that ...
1
vote
2answers
47 views

Is the longest Hamiltonian cycle NP-complete?

As I understand it to prove something is NP-complete you have to show that it's NP-hard by reducing and a known NP-complete problem to your problem and also prove that it is in NP which you do showing ...
1
vote
1answer
50 views

Why is this NP complete?

I am looking at the diverse subset problem in Kleinberg and Tardos, shown in the image: Why can't we give a polynomial time algorithm for this? Cant we iterate through each person a, and then each ...
-1
votes
0answers
13 views

Decide if there exist two vertex set $V_1$ and $V_2$ ($V_1 +V_2 = V$) such that both $V_1$ and $V_2$ are vertex cover

Given a graph $G$ and its vertex set $V$. Considering the following problem: are there two disjoint vertex sets $V_1$ and $V_2$ ( $V_1 \cup V_2 = V$) such that both $V_1$ and $V_2$ are vertex covers ...
64
votes
7answers
15k views

Is legislation NP-complete?

I would like to know if there has been any work relating legal code to complexity. In particular, suppose we have the decision problem "Given this law book and this particular set of circumstances, is ...
0
votes
1answer
63 views

Karp hardness of minimum number of arc reversals needed to turn a graph into an Eulerian one

What is the complexity of this problem EULERIAN ARC REVERSAL Input: a directed graph $G(V,A)$ and an integer $k$ Output: YES if $k$ arc reversals are enough to transform $G$ into an ...
0
votes
0answers
24 views

Transforming bin packing problem into weight distribution problem

I am working on a problem and need help to iron details and help to move it forward. P1: There are $n$ items with weights $w1, w2, .., wn$ and $K$ people ($p1, p2, .., pk)$ needs to carry these ...
2
votes
1answer
68 views

Proving that Hamiltonian Cycle is reducible to a travelling problem?

I chanced upon the following question online: A company has two trucks, and must deliver a number of parcels to a number of addresses. They want both drivers to be home at the end of the day. ...
1
vote
1answer
82 views

Proving problem NP-completeness [duplicate]

I am studying computational complexity and i am trying to solve this problem. We are given a (non-bipartite) complete graph: G = (V, W, E) where the vertices can be divided in two classes V and W ...
2
votes
0answers
18 views

Is finding a sum of two squares representation for a number computationally assymptotically equivalent to integer factorization?

I have been wondering this question because given a number $n$ with prime factors of the form $4k+3$ when we square $n$ and find a sum of two squares which should reveal these types of factors (as ...
1
vote
1answer
21 views

NP-completeness and reduction of MAX-XOR-SAT and MAX-2-XOR-SAT

It is often stated that the MAX-XOR-SAT problem is NP-hard, and that likewise is the MAX-2-XOR-SAT problem. However, I cannot find a reduction from SAT to either of these problems, nor a proof of NP-...
1
vote
1answer
15 views

NP-Completeness reduction, using a same input

We have problem X and Y that we know is NP-Complete. Problem X uses graph G as an input and Problem Y uses graph G and constant k as an input. Problem we are trying to reduce to, which I will call Z, ...
2
votes
1answer
24 views

NP-Hard on Complete Graphs

I have a problem (A) on undirected graphs that I wish to show is NP-Hard. I can show that there is a reduction from a well known NP-Hard problem (B) to A by constructing an instance of A with a ...
1
vote
1answer
31 views

Variant of an approximation algorithm for vertex cover

Here is an approximation algorithm that finds vertex cover of a graph. ...
1
vote
1answer
39 views

What is the usage of a decision problem for an optimization problem like the longest path problem?

I just read this definition for the longest path problem: LONGEST PATH Input: A graph $G=(V,E)$, an integer $k$. Question: Is there a path with at least $k$ vertices in $G$ This seems a ...
0
votes
0answers
69 views

Is it a bin-packing problem?

Several descriptions I found for the bin-packing problem. One says: In the bin packing problem, objects of different volumes must be packed into a finite number of bins or containers each of volume ...
0
votes
1answer
108 views

How can I show that a problem is not $NP$

Consider the following image: The problem is: can we cover the bigger rectangle with small rectangles such that no two rectangles overlap and no gap opens up? Prove that this problem is $NP-Hard$. I ...
1
vote
1answer
43 views

First problem to be considered np complete?

What is the first problem that was demonstrated to be NP-Complete?
1
vote
2answers
83 views

If P = NP, can all NP problems be solved within time $O(n^k)$ for fixed $k$?

I came across this question while studying for an exam: T/F: Suppose we can show for some fixed $k$, an NP-complete problem P has a time $O(n^k)$ algorithm. Then every problem in NP has a $O(n^k)$ ...
1
vote
1answer
25 views

Complexity of two cycles which differ by $1$ in length

Given an undirected graph $G(V,E)$, our problem asks whether $G$ contains $2$ simple cycles which differ by $1$ in length. What is the complexity of this problem?
2
votes
1answer
59 views

Is SAT known to be non-context-free or even non-regular?

We have seen various languages proven to be outside of REG and CFL by corresponding pumping lemmas. Has something similar been done for SAT?
1
vote
1answer
32 views

Subset sum exponential solution - how does the sorting work?

The wiki for the subset sum problem found here it states that you take the list of N elements and split it into two lists of N/2 elements. You then generate all the subsets for each list (each having ...
0
votes
2answers
91 views

Reduce EXACT 3-SET COVER to a Crossword Puzzle

I have an assignment where I have to prove that solving a crossword puzzle is an $NP$-complete problem by reducing from EXACT 3-SET COVER. I have more or less given up at this point. If anyone could ...
0
votes
0answers
19 views

Implication of Mahaney's Theorem

Not having received an answer to this question on Math.SE, I am asking it here. According to this source, Mahaney’s Theorem states that: An $NP$-complete language $L$ is Karp-reducible to a sparse ...
1
vote
1answer
19 views

Many-One Reducibility of decision problems for complexity theory?

A many-one reduction of problem $A$ to problem $B$ is essentially a function that converts a problem instance in problem $A$ to an instance in $B$. This allows you to use a $B-$solver one time to ...
2
votes
1answer
19 views

Positioning items to maximize separation

Say we want to place n items on the real line. Let us denote the position of item i by $p_i$. We have interval constraints on the position $p_i$, i.e. we are given $l_i, r_i$ such that $l_i \le p_i \...
2
votes
3answers
478 views

What will happen to NP-Hard problems if P=NP

I was going through the lecture of prof. Erik Demaine and he said that a problem X is NP-Hard if it is at-least as hard as every problem Y that belongs to NP class. He further said that if we can ...
2
votes
2answers
82 views

Complexity of finding Exact Size Cut-Sets in Bipartite Graphs

I am interested in the problem of deciding if a cut-set of a given size $k$ (i.e. the number of edges crossing the partitions is $k$) exists in a given bipartite graph (both the graph and $k$ are part ...
1
vote
1answer
50 views

Karp hardness of directed monochromatic triangle problem

Monochromatic problem is a classic NP-complete problem. Does the complexity stay NP-complete if we use directed graph? DIRECTED MONOCHROMATIC TRIANGLE problem: Input: A digraph $G(V,A)$ ...