8
votes
Accepted
Proofs of reduction of any hard problem
The first "approach" is the definition of a polynomial time many-one reduction. This is the type of reductions used for defining NP-hardness: a problem $B$ is NP-hard if for every problem $A$...
- 277k
6
votes
Accepted
Is there such a notion as "effectively computable reductions" or would this be not useful
Nice question! I think that your notion of an "effectively computable reduction" is interesting and worth studying, but not as fundamental as standard reductions. Let me provide some observations ...
- 7,068
5
votes
Accepted
SAT satisfaction with 10 variables
The problem you mentioned is in $P$ so it is not NP-complete. We know that $|\phi| = n$ so the number of variables is less than $n$ and we know that members of $A$ exactly have 10 True assignments. So ...
- 537
5
votes
Accepted
Prove finding k disjoint paths from n given paths in a directed graph is NP-complete
Membership of your problem in $\mathsf{NP}$ is trivial. To prove that it is also $\mathsf{NP}$-hard consider an instance of (the decision version of) independent set consisting of a graph $G=(V, E)$ ...
- 29.5k
5
votes
Accepted
CLIQUE $\leq_p$ SAT
There are many ways to reduce CLIQUE to SAT. Probably the simplest is as follows. Suppose that we have a graph $G = (V,E)$, and interested in a $k$-clique. We will have $k|V|$ variables $x_{iv}$, ...
- 277k
5
votes
Given the optimal coloring of a graph how will we find the optimal coloring of its complement graph?
Morandini, NP-complete problem: partition into triangles shows that the following problem is NP-complete: Given a tripartite graph $G$ on $3n$ vertices (given together with a tripartition), determine ...
- 277k
4
votes
Concrete example of Vertex Cover to Subset Sum reduction
In Computational Intractability, we often come across a need to reduce Vertex Cover (VC) problem to a Subset Sum problem...
We do?
... mostly to prove Subset Sum is NP-Complete.
There's no ...
- 81.7k
4
votes
Interpretation of co-NPCompleteness?
As far as I understand your problem statement is as following:
Given a Problem $A$ that has an answer $true$ if and only if both (some) conditions 1 or 2 are $false$.
We have a decision problem $A(...
- 9,837
4
votes
Accepted
Definition of NP-hardness for non-decision problems
There is a slight abuse of notation going on. We say that a function $f$ is NP-hard if $f\in FP$ implies $P=NP$. For example, if $L$ is NP complete and $M_L(x,y)$ is a verifier for $L$, then any ...
- 13.4k
4
votes
Accepted
Why is Independent Set "at least" and Vertex Cover "at most" k
Theory
Note that the set of all vertices is trivially a vertex cover, and any set containing only one vertex is trivially an independent set.
What is hard with an independent set is to make it larger. ...
- 530
3
votes
Accepted
Is Monotone 3-SAT with exactly 3 distinct variables untractable?
I will try to answer now my own question and would be glad about some feed back concerning the corectness.
Like in the question above discussed and pointed out by Kyle Jones we can reduce arbitrary 3-...
- 165
3
votes
Accepted
Solving Exact2IS using IS
First of all, if you can determine whether a graph $G$ contains an independent set of size $k$, then you can also find such a set efficiently. This is known as "search-to-decision reduction". Here is ...
- 277k
3
votes
Reducing Vertex Cover to Half Vertex Cover
Let special vertex cover be the special case of vertex cover in which $|V| = 2k+1$. We later reduce vertex cover to special vertex cover.
Now suppose we're given an instance $G = (V,E),k$ of special ...
- 277k
3
votes
vertex cover reduction to subset sum
For simplicity write all the numbers in base $4$. Fix an arbitrary ordering of the edges of the graph $G$ and let $e_i$ be the $i$-th edge ($i= 1, \dots, |E(G)|$).
For each vertex $v \in V(G)$ define ...
- 29.5k
3
votes
Why can KARP reductions be used to define completeness for complexity classes in the polynomial hierachy?
Suppose that $f$ is the polynomial reduction between $L'$ and $L$, i.e. $x \in L' \Leftrightarrow f(x) \in L$. If $L \in \Sigma_k^p$ then $y\in L \Leftrightarrow \exists z_1 \forall z_2 \ldots M(y, ...
- 183
3
votes
Easy proof for $Primes \in NP$
Here is the definition of NP:
A language $L$ is in NP if there is a polytime machine $T$ and a polynomial $p$ such that:
If $x \in L$ then there exists $y$ of size at most $p(|x|)$ such that $T(x,y) ...
- 277k
3
votes
Accepted
Easy proof for $Primes \in NP$
As you have stated, $Composites\in NP$ and $\overline{Primes}=Composites$.
Hence, what you proved is that $Primes\in co-NP$.
There is no easy reduction $Primes\le_p Composites$, since you will have to ...
- 11.6k
3
votes
Using FFT as a black box to solve subset sum. How is this done? Given a set of numbers, S, and a target value T
For a set $S = \{s_1,\dotsc,s_n\}$. Construct a polynomial $P(x): x^{s_1} + x^{s_2} + \dotsc + x^{s_n}$.
Multiply the polynomial by itself three times, i.e., $P(x) \cdot P(x) \cdot P(x)$. Let this ...
- 6,157
3
votes
Accepted
Is there a book with 100 reductions?
The classical reference on NP-completeness is Garey and Johnson's Computers and Intractability, which contains a compendium of over 300 NP-complete problems, with links to papers proving their NP-...
- 277k
3
votes
Accepted
Maximum independent subset for graphs with lots of edges
The problem is still $\mathsf{NP}$-hard. For example, take a hard instance $G = (V,E)$ of the original maximum independent set problem. Add a new vertex set $V'$ to the graph such that $|V'| = |V|$ ...
- 6,157
3
votes
Accepted
Is finding a Polytime reduction from $L_1$ to $L_2$ equivalent to proving $L_2 \in P \Rightarrow L_1 \in P$
No, this only works one way.
If there is a polynomial time reduction from $A$ to $B$, then $B \in P \implies A \in P$. This works irrespective of the what kind of languages $A$ and $B$ are.
The ...
- 211
3
votes
Bipartite matching with constraints on one part
The problem is not approximable in polynomial-time within a factor of $n^{1-\varepsilon}$ for any constant $\varepsilon>0$, unless $\mathsf{NP} = \mathsf{ZPP}$.
To see this you can reduce from ...
- 29.5k
3
votes
Accepted
Reduction from dominating set to disconnected dominating set
Consider an undirected graph $G = \langle V, E\rangle$, and consider a dominating set $S\subseteq V$ in $G$. If you mean by "$S$ is disconnected" that the subgraph induced by $S$ is not ...
- 2,911
2
votes
Accepted
Are every problems in EXP karp reducible to any EXP-Complete?
Are every problems in EXP karp reducible to any EXP-Complete?
Yes. That's the definition of $\mathrm{EXP}$-completeness.
My question is: where is my mistake?
Your mistake is in believing that $L''...
- 81.7k
2
votes
If $Q$ reduces to $L$ then $\overline{Q}$ reduces to $\overline{L}$
By hypothesis $Q \le_p L$, i.e., there exists a poly-time computable function $f(x)$ such that $x \in L \iff f(x) \in Q$. Then:
$$
x \in \overline{L} \iff x \not\in L \iff f(x) \not\in Q \iff f(x) \...
- 29.5k
2
votes
Reducing Vertex Cover to Half Vertex Cover
In addition to the reduction given by Yuval Filmus, you can also use the following reduction, which avoids blowing up the size of $G$ to $\Theta(|V| \cdot |E|)$.
Assume w.l.o.g. that $k<|V|$ (...
- 29.5k
2
votes
Polynomial-Time reduction from Partition to MakeSpan
Given an instance of partition (i.e., a set of numbers) $\{a_1, \dots, a_n\}$ create an instance of Job Scheduling (what you call Makespan) with $2$ machines and $n$ jobs $j_1, \dots, j_n$, where the ...
- 29.5k
2
votes
Accepted
Converting a Mixed SUBSET-SUM Problem To All-Positive Case
Both variants are NP-complete, so such a reduction surely exists: the definition of NP-completeness guarantees it.
If you want an explicit reduction, you can reduce one to the other (reduce to 3SAT ...
D.W.♦
- 159k
2
votes
Accepted
Confusion in Reduction of Hamiltonian-Path to Hamiltonian-Cycle
If the vertex $u$ is not added to to $G'$, then a Hamiltonian cycle in $G'$ does not necessarily correspond to a Hamiltonian path from $s$ to $t$. This is because the cycle may not have $s, t$ ...
- 111
2
votes
Accepted
Reduction from VC to {a,k | a is a 3DNF (disjunctive normal form) and there exists an assignment satisfying exactly k clauses in a}
The reason for why you are having problems is because your solution does not work. In particular, the problem is that your formula does not capture the VC problem statement. More precisely, the ...
- 1,526
Only top scored, non community-wiki answers of a minimum length are eligible