Stack Exchange Network

Stack Exchange network consists of 175 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]

Questions about decision problems that can be solved on nondeterministic Turing machines in time polynomial in the length of the input.

2
votes
2answers
76 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
61 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
39 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
33 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
83 views

Is this partitioning problem NP-complete?

I have a sequence of points $(x_1, \ldots, x_n)$ and a function $f$ that maps every consecutive subsequence (ie. of the form $(x_i, x_{i+1}, \ldots, x_j)$) to a real number. I want to split this ...
1
vote
1answer
43 views

How to show that this decision problem is in co-NP?

Given a set of strictly positive numbers $a_1, ..., a_n$, the problem is to determine if $\lfloor n/2 \rfloor$ different indexes $i_1, ..., i_{\lfloor n/2 \rfloor}$ exist so that $$\frac{a_{i_j}}{a_{...
0
votes
1answer
41 views

Why proving the solution of a problem is polynomial time is sufficient enough to say that it is a NP prolbem? [duplicate]

Why proving that we can verify the solution of a problem is polynomial time is sufficient enough to say that the problem is nondeterministic polynomial time? Please note: this is not a question on how ...
2
votes
0answers
18 views

Reducible from vertex cover for only some inputs

Suppose I have an NP problem, $\text{PROBLEM}(n)$, such that for certain values of $n$ I can get a reduction from vertex cover with $n$ vertices, and for others such a reduction is not possible (if $\...
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 ...
3
votes
1answer
38 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
0answers
22 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 ...
1
vote
2answers
33 views

Does NTIME($n^\alpha$) $\subset$ EXPTIME imply NP $\subset$ EXPTIME?

I think I'm able to prove NTIME($n^\alpha$) $\subset$ EXPTIME for arbitrary $\alpha$. Is this a new result? If it was, would there be a way to deduce NP $\subset$ EXPTIME from it?
1
vote
0answers
24 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?
1
vote
1answer
21 views

Verifier for A_tm in polynomial time - how to formally prove it does not exist?

How would you formally prove the non-existance of a polynomial time verifier for $A_\mathrm{TM}$? I mean we can't just say that in order to read a certain certificate we need more than poly-time ...
1
vote
1answer
28 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
0answers
113 views

Proving there is no polynomial algorithm for independent set

I need some guidance in an assignment I'm doing. I'm at complete loss, he says the the MAXIMUM INDEPENDENT SET problem is NP-hard and then asks me to prove that there is no polynomial time for the ...
0
votes
2answers
46 views

Is the verifier for an $NP$ and its $co-NP$ the same?

I have a hard time to find the goal of having $co-NP$ problems. $NP$: Is there a Hamiltonian path in this graph? We need to bring a certificate, and the verifier checks the certificate in ...
1
vote
2answers
54 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 ...
0
votes
1answer
27 views

What is the concept of “encoding” in NP-completeness

Hi I have been reading Ch 34(NP-Completeness) Section 34.1 of CLRS and I am confused why do we need to consider different encodings. Everything is represented as binary at the end so why consider ...
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
2answers
42 views

How does a co-NP problem differ from an NP (its complement) one?

I have quite a hard time understanding co-NP problems. If we can reduce every problem to decision problem. NP problems should accept YES instances -> instances where the answer is yes. So for example ...
1
vote
1answer
83 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 ...
1
vote
2answers
34 views

Understanding Hamiltonian Path, NP vs Co-NP

I am having difficulty understanding the distinction between NP and Co-NP. According to my textbook (Sipser), the HAMPATH problem is in NP. That is, for the language: HAMPATH = { (G,s,t) | G is a ...
0
votes
1answer
90 views

2SAT Problem using Implication Graph

I was doing a practice question. As you can see below there is an Implication graph. To check whether the problem is satisfiable, I checked whether there were any 'bad loops'. To do so, for each ...
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
84 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
3answers
88 views

The most subtle NP-“intermediate” problem

What is the $NP$ problem which status (in $P$ or $NP$-complete) is still unsettled, as of 2018? This question is inspored by the following two recent breakthroughs: The work of Mulzer et. al on $NP$-...
2
votes
3answers
550 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
91 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)$ ...
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}...
1
vote
2answers
49 views

Avoiding the trivial certificate in complexity class NP

One definition of the class NP is that there is a certificate whose size is bounded by a polynomial function of the problem instance size which can be used on a deterministic TM, along with the ...
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
41 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
2answers
67 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, ...
1
vote
1answer
43 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{...
0
votes
1answer
35 views

Karp hardness of an equidistant set in digraph

Following the success of the undirected version: Karp hardness of an equidistant vertex set Inspired by the success of this long ago question: NP-hardness of problem with indices and subsets We ...
1
vote
1answer
112 views

Is this a correct way to show that a problem is coNP-complete?

Let $A$ be a problem that I want to show it is coNP-complete. I know I could just show its complement $\bar{A}$ is NP-complete or that $\bar{A}$ is in NP and for some coNP-complete problem $Q$, show ...
1
vote
0answers
44 views

Karp hardness of a simply equidistant vertex set

Following the success of the previous question: Karp hardness of an equidistant vertex set I continue to propse yet another computational problem. This time, we modify the notion of an equidistant ...
0
votes
1answer
60 views

Why checking if tuple belongs to join of two tables is NP-complete?

I have read that checking if tuple belongs to join of two tables is NP-complete. I had computional-complexity activities during my studies, I remember basics, however I have forgotten details. ...
2
votes
1answer
63 views

Karp hardness of an equidistant vertex set

What is the hardness of the following problem? Input: An undirected graph $G(V, E)$ and a natural number $k$ Output: YES if $G$ has an equidistant vertex set of size $k$, otherwise NO $\...
0
votes
0answers
27 views

Edge-midpoints cover with radius 1

This is in a series of posts. Previous quetion: Vertex cover with covering radius 2 Other series: Karp hardness of searching for a matching split In this problem, our cover for a given undirected ...
4
votes
1answer
50 views

Vertex cover with covering radius 2

Our problem is: Given an undirected graph, does it have a vertex cover consisting of $k$ vertices? A vertex included in this vertex cover variant will cover every edge incident to it and every edge ...
3
votes
2answers
81 views

NP languages definition

Is it good to define a language $\mathcal{L}$ in NP as a language for which, given an element $x$, it is possible in polynomial-time to check whether $x \in \mathcal{L}$ or not? Because I need to have ...
3
votes
1answer
69 views

Karp hardness of searching for a matching split

UPDATE: In 2 days, if no more convincing answer is posted, then bounty of 50 rep. will go to xskxzr. Due to lack of connectedness and a clean & clear cut, the bounty is still open for 2 days. (UTC ...