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
1answer
13 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
26 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 ...
0
votes
0answers
21 views

Reduce 3-Coloring to 3-Coloring with minimum vertex degree 4

Is there any way to reduce the 3-Coloring graph problem to a 3-Coloring problem with the condition of every vertex must have at least 4 degree? If such reduction exists, what could be an appropriate ...
0
votes
0answers
12 views

gradient and Hessian [closed]

I got this question in an assignment and I am having problems even to understand it. I would appreciate any help given. Find the gradient and Hessian of the function $ f : R^n → R$ where $ f(x) >...
-1
votes
0answers
21 views

Exact cover np-complete problem solution, contradiction by using prime numbers mapping [closed]

My current understanding of the exact cover np-complete problem leads to contradiction: Assuming there exists an exact cover in S that can be computed in polynomial time and that covers all of X, each ...
1
vote
0answers
24 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
36 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 ...
0
votes
0answers
12 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 ...
63
votes
7answers
14k 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
57 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
22 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
52 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
78 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
17 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 ...
0
votes
0answers
32 views

NP-hardness for a binary stochastic quadratic programming

I have the following optimization problem: $$\min_{\mathbf{x}} \; \mathbf{x}^T\mathbf{P}(\mathbf{x}) \mathbf{x} \\ \text{s.t.} \; ||\mathbf{x}||_1 = K$$ where $\mathbf{x} \in \{0, 1\}^N$ is a binary ...
1
vote
1answer
16 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
29 views

Variant of an approximation algorithm for vertex cover

Here is an approximation algorithm that finds vertex cover of a graph. ...
1
vote
1answer
36 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
46 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
78 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
82 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
58 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
28 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 ...
-1
votes
2answers
83 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 and if anyone ...
0
votes
0answers
18 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
407 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
79 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
44 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)$ ...
0
votes
0answers
10 views

Karp hardness of a supportive clique in digraphs

In a directed graph (digraph) $G(V,A)$, a set of vertices $C\subseteq V$ is called a supportive clique if (1) for every $u\neq v$ in $C$, either $(u,v)\in A$ or $(v,u)\in A$ and (2) for every $u\in C$,...
0
votes
1answer
21 views

Karp hardness of a diameter-decreasing planted clique

A diameter-decreasing planted clique in an undirected graph $G(V,E)$ is a set of vertices $\mathcal{C}\subseteq V$ such that if we add all the missing edges between any pair of vertices in $\mathcal{C}...
7
votes
1answer
63 views

Is distinguishing Hadamard matrices _really_ NP-hard?

In a few different places ( http://www.ams.org/journals/mcom/2004-73-246/S0025-5718-03-01539-4/S0025-5718-03-01539-4.pdf and https://books.google.com/books?id=qYYKBwAAQBAJ&pg=PA21&lpg=PA21&...
12
votes
2answers
3k views

If lower bound of a problem is exponential then is it NP?

Assuming that we have a problem $p$ and we showed that the lower bound for solving $p$ is $\mathcal{\Omega}(2^n)$. can lower bound $\mathcal{\Omega}(2^n)$ implies the problem in $NP$?
1
vote
1answer
44 views

For each given set choosing either it or its complement such that their union exactly has a given size

Given an integer $k$ and $n$ sets $A_1,\ldots,A_n$, denote $U=A_1\cup A_2\cup\cdots\cup A_n$, $A_i^0=A_i$ and $A_i^1=U\backslash A_i$. The problem asks whether there exists $(b_1,\ldots, b_n)\in\{0,1\}...
0
votes
1answer
48 views

Karp hardness of a clique with given number of outer-incident edges

A clique in an undirected graph $G(V,E)$ is a subset of vertices $\mathcal{C}\subseteq V$ every pair of which is adjacent $u,v\in \mathcal{C}\implies uv\in E(G)$. Given a clique $\mathcal{C}\subseteq ...
3
votes
0answers
40 views

Karp hardness of a module in a graph

DEFINITION: A set of vertices $A\subseteq V$ in a graph $G(V,E)$ is called a module if it satisfies the following property: For every $v\in V\setminus A$, either $A\subseteq N(v)$ or $A\cap N(v)=\...
1
vote
0answers
18 views

Can Fiedler vector be used for displaying an undirected graph in a sequential manner?

My problem is to display an undirected unweighted graph in a grid format ( $ (n \times 3) $ - matrix for simplicity) without compromising on the connections displayed on the screen (the only ...
0
votes
1answer
35 views

On the proof of NP-Hardness of the Cardinality Constrained Quadratic Knapsack Problem

in Polyhedral Study of the Cardinality Constrained Knapsack Problem the authors prove that the Cardinality Constrained Knapsack Problem is NP-Hard by reducing PARTITION to it. Besides, it's easy to ...
1
vote
2answers
66 views

Karp hardness of testing for homomorphisms to a fixed non-bipartite graph

Description: Suppose that we are given a fixed non-bipartite graph $H$. A graph $G$ is loopless surjectively homomorphic to $H$ if there exists a loopless surjective homomorphism $\varphi:V(G)\to V(H)$...
1
vote
1answer
38 views

Karp hardness of a vector system allocation

Given an undirected graph $G(V,E)$, a vector system is a set $S$ of ordered pair (intuitively called vector) $(u,v)$ (we shall call $u$ the initial point, and $v$ the terminal point) that satisfies ...
1
vote
1answer
32 views

Karp hardness of a guarding set in digraph

Our problem is to decide whether a digraph has a guarding set of size at most $k$. Definitions are following. A digraph $G(V,A)$ has $V(G)$ as its vertex set and $A(G)$ as its arc set. A guarding set ...
1
vote
2answers
48 views

Karp hardness of digraph coloring without monochromatic dicycle

Problem statement: Input: a digraph $G(V, A)$ and a natural number $k$ Output: YES if it is possible to color all vertices of $V(G)$ by $k$ colors such that no directed cycle is monochromatic, ...
2
votes
0answers
29 views

Highest lower bound on an NP complete problem

What is the highest time complexity lower bound that has been proven on any (non-contrived) NP complete problem?
1
vote
1answer
39 views

Assuming NP≠coNP, do we have a similar theorem to Ladner's?

We have that $\mathrm{NP\neq coNP\iff NP\neq NP\cap coNP}$. So by assuming that $\mathrm{NP\neq coNP}$, can we prove the existence of intermediate problem between $\mathrm{NP}$-complete and $\mathrm{...