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$...
Yuval Filmus's user avatar
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 ...
Caleb Stanford's user avatar
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 ...
Mohsen Ghorbani's user avatar
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)$ ...
Steven's user avatar
  • 29.4k
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}$, ...
Yuval Filmus's user avatar
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 ...
Yuval Filmus's user avatar
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 ...
David Richerby's user avatar
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(...
fade2black's user avatar
  • 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 ...
Ariel's user avatar
  • 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. ...
Stef's user avatar
  • 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-...
Pepe's user avatar
  • 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 ...
Yuval Filmus's user avatar
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 ...
Yuval Filmus's user avatar
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 ...
Steven's user avatar
  • 29.4k
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, ...
diplodocus's user avatar
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) ...
Yuval Filmus's user avatar
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 ...
nir shahar's user avatar
  • 11.5k
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 ...
Inuyasha Yagami's user avatar
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-...
Yuval Filmus's user avatar
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|$ ...
Inuyasha Yagami's user avatar
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 ...
1001's user avatar
  • 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 ...
Steven's user avatar
  • 29.4k
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 ...
Bader Abu Radi's user avatar
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''...
David Richerby's user avatar
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) \...
Steven's user avatar
  • 29.4k
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|$ (...
Steven's user avatar
  • 29.4k
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 ...
Steven's user avatar
  • 29.4k
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.'s user avatar
  • 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$ ...
Richie Yeung's user avatar
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 ...
Watercrystal's user avatar
  • 1,526

Only top scored, non community-wiki answers of a minimum length are eligible