5

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)$ with $|V|=n$ and of an integer $k$. Construct the graph $H = (V', E')$ where $V' = V \cup \{ x_{u,v} \, : \, (u,v) \in E \}$ and $E' = V' \times V'$. For each $...


5

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 about this notion that may be illuminating: Observation 1: it does not make sense to talk about effectively computable reductions from one language to another; ...


5

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 by a brute force algorithm check every possible assignment to variables. Choose 10 variables from n, $(^{n}_{10})$ and set them to $True$ and set other ...


5

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 function $f$ which maps $x$ to some $y$ such that $M_L(x,y)$ whenever such $y$ exists is of course NP-hard in this sense. We don't usually talk about actual ...


4

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 the basic idea. Choose an arbitrary vertex $v$, and remove it. If the graph still has an independent set of size $k$, then keep going. Otherwise, all ...


4

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 particular reason to go down that route. Karp [1] defined the Knapsack problem as: given $a_1, \dots, a_r, b\in\mathbb{Z}$, is there a set $S\subseteq \{1, \dots,...


3

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 vertex cover. Construct an instance $G',k$ of half vertex cover by attaching $|E|$ new edges to each vertex in $V$. The total number of edges in the new graph ...


3

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, z_1, \ldots z_k) = 1$. Then $$x\in L \Leftrightarrow f(x) \in L \Leftrightarrow \exists z_1 \forall z_2 \ldots M(f(x), z_1, \ldots z_k) = 1 \Leftrightarrow \...


2

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''\notin\mathrm{EXP}$. You've demonstrated a Turing machine that decides $L$ in time $O(n^{\log n}) = O(2^{(\log n)^2})\subset O(2^n)$. I'm not sure what you ...


2

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}$, whose intended meaning is "the $i$th vertex of the clique is $v$". The constraints are: There is an $i$th vertex: for all $1 \leq i \leq k$, $\bigvee_{v \in V} x_{...


2

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|$ (otherwise the reduction is trivial) and that the instance (graph) $G = (V,E)$ of vertex-cover contains a vertex $v \in V$ of degree $1$ (otherwise you could append ...


2

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) \in \overline{Q}. $$ Therefore $\overline{L} \le_p \overline{Q}$.


2

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 formula you build always has assignments satisfying $k$ clauses by just setting $k$ variables to true and the rest to false. So let $G = (V, E)$ be a graph and $X \...


2

You will not find a reference for "the standard definition" of NP-hardness. Some authors restrict the notion "NP-hard" to decision problems only, and use the definition of reduction you mention in your question (which is sometimes referred to as a "Karp reduction" or "many-one reduction"). Other authors use the term ...


2

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 using Cook's theorem, then reduce 3SAT to the other using its NP-completeness). The resulting reduction will be ugly, though, so I suspect this might not be what ...


2

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-SAT formulas to monotone 3-SAT formulas. For example a clause $C=(x_1\vee x_2 \vee \neg x_3)$ can be converted to $C'(x_1\vee x_2 \vee z_3)\wedge (z_3 \vee x_3) ...


2

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 execution time of the $i$-th job is $a_i$. Pick $b = \frac{1}{2} \sum_{i=1}^n a_i$. If there is a solution to the partition problem, i.e., a set $A \subseteq \{...


2

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$ adjacent to each other. For example, one could have Since there is no Hamiltonian path from $s$ to $t$ in the first graph, there is no Hamiltonian cycle in the second ...


1

First the reduction from P2 to P1 is easy cause if you can decide whether there is one cycle you can also decide whether there is at least one cycle. The other way around is more tricky. Notice that P1 can be solved in polynomial time if we have an oracle for P2 (an oracle for P2 means that we can use a subroutine that solves P2). algorithm for P1 with input ...


1

Hint: Suppose that $G$ already had a Hamiltonian cycle, but no Hamiltonian path from $s$ to $t$. OK, this clearly needs more explanation. Consider the case of an undirected cycle graph with 4 vertices. This graph, $G$, has a Hamiltonian cycle, but it does not have a Hamiltonian path from $0$ to $2$. Now add an edge $(2,0)$, to obtain a new graph, $G'$. This ...


1

Let $G = (V,E)$ be an instance of $3$ coloring. Construct an instance $\phi$ of 3-SAT as follows. For each vertex $v \in V$ create $3$ variables $v_a, v_b, v_c$ representing the $3$ possible ways to color of $v$. For each vertex $v \in V$ create the clauses $(v_a \vee v_b \vee v_c) \wedge (\overline{v_a} \vee \overline {v_b}) \wedge (\overline{v_b} \vee \...


1

If you're not really sure whether a reduction will work, it probably won't. Whenever you are making a reduction you should always have a plan of how to prove it correct. In this case, we're looking to see whether $1^2+2^2+3^2+...+n^2$ can be written as a sum of squares in some other way (which would be a false positive). We have that $4^2=2^2+2^2+2^2+2^2$. ...


1

Thanks to comments by Yuval Filmus, I understand that my question does not make sense as Karp reductions are defined for decision problems. Since Cook reductions allow more freeness, it makes sense to talk about a Cook reduction from a decision problem to an optimization problem, but this is not true for Karp reduction.


1

Here is a more general theorem: Let $X$ be some NP-complete problem. Then $X$ can be solved in polynomial time iff all problems in NP can be solved in polynomial time. Indeed, if all problems in NP can be solved in polynomial time, then since $X$ is in NP, then $X$ can be solved in polynomial time. In the other direction, suppose that $X$ can be solved ...


1

As stated in the comments, every problem is reducible to itself (under any notion of reduction - polynomial-time many-one reduction, polynomial-time Turing reduction, ...). It's worth noting that when thinking about many-one reductions there are two important "edge cases" to consider: No nonempty set is many-one reducible to $\emptyset$. No set other than ...


1

No. As a counterexample pick any non-trivial problem $P_2$, i.e., a problem with at least one yes instance $I_{\text{yes}}$ and at least one no instance $I_{\text{no}}$. To reduce an instance $I_1$ of $P_1$ to an instance $I_2$ of $P_2$ first solve $I_1$ (e.g., by brute force). If the answer to $I_1$ is yes, then let $I_2 = I_{\text{yes}}$, otherwise $I_2 = ...


1

For the first one, since $A \leq_p B$, there must exist a function $f \in \operatorname{FP}$, such that $x \in A$ if and only if $f(x) in B$ for an arbitrary word $x$. We can prove that $f$ is also a reduction from $\overline A$ to $\overline B$ as follows: Let x be an arbitrary word. \begin{align} x \in \overline A &\iff\\ x \notin A &\iff\\ f(x) \...


1

If I understand correctly you only have a problem when the graph $G = (V,E)$ of the vertex-cover instance has isolated vertices. In this case you can transform $G$ into a related graph $G' = (V \cup \{x,y \}, E')$ by adding a two new vertices $x$ and $y$ such that $x$ and $y$ are connected to each other by an edge, and there is an edge between $x$ and each ...


1

Problem A is in NP if: B is in NP and you can reduce B to A in polynomial time -> B $\leq_p$ A Not quite right. The class P is a subset of NP anyway, and hence A is already NP if it is in P. The question is whether A is in P or not. By reducing B to A in polynomial time, you prove that any polynomial solution of A is a polynomial solution of B. ...


1

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 an integer $n_v$ of $|E(G)| + 1$ digits as follows: the $i$-th least significant digit of $n_v$ is $1$ if $e_i$ is incident to $v$ and $0$ otherwise; the ...


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