Questions tagged [np]
Questions about decision problems that can be solved on nondeterministic Turing machines in time polynomial in the length of the input.
1
vote
1answer
37 views
Is this problem in NP?
I am new in complexity theory and have a doubt.
If you have a language (alphabet) L (for example {"a";"b";"Y","0","1","◄"}) and a Dictionary D (for example {"abY";"Ú■";"ba";"000001◄";"FFG","342"}) ...
1
vote
2answers
234 views
Is the language {<p,n> | p and n are natural numbers and there's no prime number in [p,p+n]} belongs to NP class?
I was wondering if the following language belongs to NP class and if its complimentary belongs to NP class:
\begin{align}
C=\left\{\langle p,n\rangle\mid\right.&\ \left. p \text{ and $n$ are ...
1
vote
1answer
70 views
A tricky P=NP problem
Define an operator $\pi(\cdot)$: for a language $L$, $\pi (L)$ is the set of all prefixes of strings in $L$ with length at least half of the original string. Prove that if $\mathsf{P}$ is closed under ...
-1
votes
0answers
35 views
Three Shopping Bag Problem
How can we prove that we can use partition to prove three bag problem is np-complete.
Three Bag problem: How can we fit m items into 3 bags, if each bag can hold upto B grams of weight
We can reduce ...
0
votes
0answers
43 views
P Langauage to NP Reduction in Polynomial Time [duplicate]
Let L be a language in P. Prove it is polynomial time reducible to any language in NP, including any language in P, which contains at least one string but doesn’t contain all the strings.
I tried ...
0
votes
0answers
23 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?
2
votes
1answer
70 views
Reduction to a vertex cover problem-like with weighted vertices and edges
Description
Let us define a new problem with an instance $I = (G = (V, E), K, L)$, whereas:
$G$ is an undirected graph
$K \le |V|$
$L > 0$ is the maximum limit
Each vertex $v \in V$ has a weight $...
0
votes
0answers
12 views
Proving k-partition problem is NP [duplicate]
For any integer k ≥ 2, the k-Partition problem is said to be a sequence of positive integers (w1, w2, . . . , wn), is it possible to partition them into k groups having equal sums?
I'm confused on ...
1
vote
2answers
48 views
Can someone explain why the MAX-CUT problem is in NP?
Given an undirected graph $G = (V, E)$ and an integer $k$, is there a partition of the vertices into two (nonempty, nonoverlapping) subsets so that $k$ or more edges
have one end in each subset?
I'm ...
2
votes
1answer
35 views
Dominating set of given size $k$ in $O(2^k |V| |E|)$
Recently I've encountered an interesting case of dominating set problem: given an unweighted and undirected graph $G(V, E)$ and knowing that it contains a dominating set of size $k$, find any such ...
1
vote
1answer
39 views
Does a polynomial solution to weakly-NP Complete problem mean P = NP?
Suppose someone finds a polynomial solution to weakly-NP Complete problem does that mean P = NP.
3
votes
1answer
39 views
If $NP\subseteq DTIME[n^{O(\log n)}]$ then what happens?
If $NP\subseteq DTIME[n^{O(\log n)}]$ then what happens? Does it imply $NP\neq EXP$? Is there any other consequences such as $BPP\neq EXP$? Does it also give $PSPACE\subseteq DTIME[n^{O(\log n)}]$?
2
votes
1answer
114 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 ...
1
vote
1answer
14 views
Show: “Checking no solution for system of linear equations with integer variables and coefficients” $\in \mathbf{NP}$
I've been struggling for a while trying to solve this problem:
Show that the following problem is in $\mathbf{NP}$:
Check that a system of linear equations with $m$ integer variables and
integer ...
2
votes
2answers
149 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
75 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
48 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
90 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
44 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
43 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
42 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
24 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
36 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
26 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
27 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
35 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
140 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
59 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
85 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
30 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
66 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
47 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
92 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
37 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
121 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
44 views
First problem to be considered np complete?
What is the first problem that was demonstrated to be NP-Complete?
1
vote
2answers
88 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
27 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
91 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
745 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
123 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
54 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
1answer
55 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
43 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)=\...
