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]

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

1
vote
0answers
37 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
0answers
19 views

Aproximation of longest path in undirected graph from given point

I'm looking for a algorithm suitable to find possibly the longest path (by count of nodes) in given undirected graph and starting node in some time resime. Is there any know algorithm for that?
0
votes
2answers
37 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 ...
-2
votes
0answers
19 views

number of turing machines with limited memory and time [on hold]

what is the number of different turing machines which can execute only on a limited memory with M cells and execute only T steps per each inputs with {0 , 1} alphabet?
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 ...
0
votes
0answers
47 views

Elimination ordering generated by Min-Fill

Is every elimination ordering generated by Min-Fill heuristic the optimal one in terms of fill-in edges? In other words, does there exist any other elimination ordering not generated by Min-Fill ...
0
votes
1answer
26 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
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
2answers
30 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
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 ...
1
vote
2answers
30 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
62 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 ...
0
votes
0answers
40 views

Using Implication Graph to check 2-Satisfiability

I have the following boolean formula: {x,y},{-x,-y},{x,-y}, and below is the corresponding Implication graph: I know that the next step is to check for 'bad loops'/Strongly Connected Components. ...
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
3answers
84 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
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}...
1
vote
2answers
39 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
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
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, ...
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{...
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
88 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
57 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
64 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
67 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 ...
3
votes
1answer
35 views

Karp hardness of searching for a matching erosion

First, read the previous question: Karp hardness of searching for a matching cut As mentioned in the supposed-to-be-comment answer in that question, without the requirement of cardinality $k$, the ...
4
votes
2answers
87 views

Karp hardness of searching for a matching cut

Follow-up question in the series: Karp hardness of searching for a matching erosion Karp hardness of searching for a matching split Maximum Matching Cut problem Input: An undirected graph $G(...
1
vote
1answer
22 views

Hardness of $2$ edge-disjoint spanning trees decomposition

The question is clear from the title. What is the complexity of the following decision problem: Input: An undirected graph $G(V, E)$ Output: $\mathrm{YES}$ if $G$ can be decomposed into two ...
0
votes
1answer
53 views

Relation of P vs. BPP and P vs. NP

What are the consequences of proving some relation ($\subseteq$, $\subset$, $=$, or $\neq$) on one of the following, to the other? $P$ vs. $BPP$ $P$ vs. $NP$
0
votes
3answers
27 views

Collection of meta-reductions in theory of $\mathrm{NP}$-completeness

I want to start a wiki post about meta-result of meta-reductions in the theory of $\mathrm{NP}$-completeness. This can be regarded as a reference request post. Any links are appreciated. At least, ...
0
votes
1answer
48 views

Does indirect diagonalization a relativize technique?

My main question is can with R.kanon , Fortnow ,... technique that shows lower bounds for SAT seperate P and NP ? Baker-Gill-Solovay showed that $P?=NP$ could not be solved with relativization. Does ...
0
votes
1answer
28 views

Cook completeness of a variant of Vertex Cover

Is this variant of Vertex Cover Cook-complete for $\mathrm{NP}$? Input: An undirected graph $G(V, E)$ together with a vertex cover $C\subseteq V$ Output: YES if there exists a vertex cover $C'\...
0
votes
1answer
143 views

A directed graph colored path problem?

Given: A rooted, directed, a-cyclic graph $G$. Let $r_0$ be the root node and $t_0$ be another target node. Each node in $G$ is assigned a non unique id/color ($ID_i),\ 1<i<N$ for some integer N....
0
votes
1answer
31 views

Is there any interesting consequence of $\mathrm{DLogTime}$-uniform ${\mathrm{Mod}_6}^0=\mathrm{NP}$

$\mathrm{NP}$ has not been separated from constant-depth circuits consisting of solely $\mathrm{Mod}_6$ gates. So, the question is whether current techniques are enough to deduce interestingly ...
0
votes
0answers
52 views

Finding reduction to prove that a language is NP-complete

I need to prove that the following problem is NP-complete: We have $n$ diplomats from $n$ countries and we need to seat them around a round table. We also get a list of diplomats who don't get along ...
0
votes
0answers
28 views

Is it true that $NP^{NP}=NP$, or it is true just if there is an assumption that $NP=CO-NP$? [duplicate]

Is it true that $NP^{NP}=NP$, or it is true just if there is an assumption like $NP=CO-NP$? I was proving that $NP^{NP}=NP$ by using the assumption that $NP=CO-NP$ but it seems that it might by ...