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 about decision problems that can be solved on nondeterministic Turing machines in time polynomial in the length of the input.

0
votes
0answers
7 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$,...
1
vote
1answer
14 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}...
2
votes
0answers
32 views

Non-constructive $NP$-completeness proof

Is there any known $NP$-complete problem which hardness proof is non-constructive. A constructive $NP$-completeness proof is a proof that $L_1\leq_p L_2$ by a reduction $r$ and from the argument ...
1
vote
2answers
35 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 ...
1
vote
1answer
43 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 ...
4
votes
0answers
37 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)=\...
2
votes
2answers
63 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)$...
2
votes
1answer
35 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 ...
2
votes
1answer
24 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 ...
2
votes
2answers
39 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, ...
3
votes
1answer
35 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{...
1
vote
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
66 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 ...
2
votes
0answers
35 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 ...
1
vote
1answer
32 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. ...
3
votes
1answer
59 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 $\...
1
vote
0answers
21 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 ...
6
votes
1answer
45 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
56 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 ...
4
votes
1answer
65 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 ...
4
votes
1answer
33 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 ...
6
votes
2answers
82 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(...
3
votes
1answer
20 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
34 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$
1
vote
3answers
20 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
39 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 ...
1
vote
1answer
26 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
141 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....
1
vote
1answer
30 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
46 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 ...
1
vote
1answer
24 views

A problem that is computable yet doesn't lie in NP?

I'm trying to find a problem that is computable but not in NP. I checked and I havent found any duplicates(I hope so too). We were asked if there is a problem that exists that is computable yet ...
1
vote
1answer
100 views

P vs NP problem (Student example)

Hello dear stackexchangers, I have a simple question, and I would like to say that I am not a scientist. When I read the problem statement on this link: http://www.claymath.org/millennium-problems/p-...
0
votes
2answers
70 views

Can we reduce an NP to an NP Problem?

Lets say Problem A,B are in NP. Can we reduce Problem A to B? Meaning A $≤_p$ B? or A $≤_t$ B Is there a difference in "hardness" of a Problem even in NP? Or must Problem B at least be NP-Complete?
0
votes
0answers
18 views

Karp Reduction L1 ≤p L2

Given: $L_1 = \{0^k1^k|k \in \mathbb{N}\}$ $L_2= \{1\}$ $L_1 \leq_p L_2$ There must be a function $$f:Σ^* \rightarrow Σ^*$$ such that $$w \in L_1 \iff f(w) ∈ L_2$$ Let's say a word in $L_1$ is ...
1
vote
2answers
36 views

NP Class Definition of a Certificate

Given the definition for all x ∈ Σ∗ x ∈ L ⇔ ∃ u ∈ Σ∗ with |u| ≤ p(|x|) and M(x, u) = 1 Lets say the input x = ababab Then the certificate u shouldn't be longer than p(|x|). But what would be p(|...
0
votes
2answers
44 views

Is finding all primes less than n, doable in polynomial time?

Bear in mind I'm almost a complete noob at complexity theory. I was reading about how AKS Primality shows that numbers of size n can be shown to be prime or composite in polynomial time. Given that, ...
7
votes
1answer
95 views

Is writing a number as two squares and writing the factors of a number equally hard?

Let $L_1$ and $L_2$ be the following: $L_1=\{r:\exists x,y \in \mathbb{Z} \text{ such that } x^2+y^2=r\}$ $L_2=\{(N,M): M<N, \exists 1<d\leq M \text{ such that d|N} \}$ Claim $L_1 \leq_P ...
3
votes
0answers
31 views

How to prove existence of the language

Consider such question: (Prove or disprove) There exists a language in $TIME(2^{n^2})$ that is not in $NTIME(n)$. I guess that answer is yes because $TIME(2^{n^2})$ and $NTIME(n)$ are totally ...
-1
votes
1answer
206 views

To prove 4-SAT CNF is NP-complete [closed]

To answer the question below, 4-SAT: Given a formula in Conjunctive Normal Form, where each clause contains exactly 4 literals, does it have a satisfying truth assignment? I was going to prove that ...
0
votes
1answer
25 views

Can we approximate the number of possible witnesses for an NP language?

Assuming $L \in NP$, meaning that L could be verified by some $V(x,y)$, such that there exists a polynomial $P(X)$ such that $|y| \leq P(|x|)$ for every $x \in L$. I was wondering - can I assume ...
0
votes
0answers
22 views

Circuit-sat reduction to 3-SAT

I'm trying to reduce this example from Circuit-sat to 3-Sat, but I got stuck. Can some one give a brief explanation step by step? Tree: schema My attempt:
1
vote
2answers
30 views

If a decision problem $A \in \text{NP}$ and there exists reduction so that $A \leq_p B$, for decision problem B, what can be deduced about B?

I think that it implies that B can be solved by a non-deterministic polynomial time or worse Turing machine, but I realise that there is possibly some greater result that I'm missing. Thanks in ...
0
votes
1answer
35 views

Reducing INDSET and MAXCUT to 3SAT

Given a graph and an integer $k$ is there an independent set larger than $k$ is INDSET problem and is there a cut larger that $k$ is the MAXCUT problem. Is there standard way to convert to 3SAT from ...
0
votes
1answer
45 views

Is this language NP Hard?

$L=\{$$($$m$,$w$,$n$$)$| $m$ is an encoding of a non-deterministic Turing machine, $w$ is any word/string in the closure of alphabet, i.e. $w\in\Sigma^*$, $n$ is any positive integer, i.e. $n\in\Bbb{Z}...
0
votes
0answers
10 views

Explain NP-Hard using an example [duplicate]

I can't grasp the concept of NP-Hard. Basically I have come accross two definitions, summarizing them this is what I understand: Applies the oncept of reducability - Transform problem A to another S, ...
0
votes
0answers
64 views

How to use SAT reductions to prove set-splitting problem is NP-Complete?

I am having a difficulty proving that the set splitting problem is NP-complete using SAT. Suppose S = {1,2,3,4} and C is a collection of subsets of S, say C1 = {1,2}, C2 = {3,4}, C3 = {1,3,4}. Each ...
0
votes
1answer
45 views

Is it immediately true that the class of P is a subset of the class NP? [duplicate]

Forgive me if this is a stupid question - it's been a while since I thought at all about complexity theory and I want to make sure that I have covered all the possible angles with regards to the ...
2
votes
2answers
125 views

Is every problem in NP?

My friend and I were studying NP-hard problems and NP-completeness. I don't think we have understood the concept very well so I thought I would come here to solve our doubt. To show that a given ...
0
votes
0answers
18 views

NP hardness - Why is one harder than the other? [duplicate]

As far as my understanding goes, to show that a problem A is NP-hard, we use another NP-complete problem B. We reduce (in polynomial time) from B to A, i.e. use A to solve B. This shows that A is ...