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