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