# Tag Info

7

Assume, w.l.o.g., that G=(V,E) is a graph without isolated vertex. Let's denote by $\mathcal{A}$ the algorithm you describe in your question. We seek to prove that given $G$, $\mathcal{A}$ outputs a minimum edge cover. Before we do that, it can be benifical to make some simple observations. First, both edge cover and matching are set of edges, and the subset ...

5

This is known as the distance-$d$ independent set, i.e., you are looking for an independent set of size $k$ where the distance between every two elements in the solution is at least $d$. The problem is NP-complete even on planar graphs according to [1], but I don't know about its complexity on partial grids. Regarding reductions, you can probably take the ...

5

No, this problem is in $\mathbf{P}$. The main point being that the sum of all the values is $1 + 2 \ldots + n = \frac{n(n+1)}{2} = \mathcal{O}(n^2)$, which is polynomial in the input size. Without the extra restriction of $v_i = i$, the sum of all the values could be exponential in the input size, as the values are represented in binary in the input. So we ...

5

You are correct. 3-clique can be solved in $O(n^3)$ time, whereas 3-coloring is NP-hard. So there can be no "poly-time reduction" from 3-coloring to 3-clique, unless $P=NP$.

4

Let $\langle G=(V, E), k \rangle$ be an instance of Independent Set, and call $n=|V|$. Let $N$ be a set of $n+1$ new vertices (not in $V$), and construct a new graph $G' = (V', E')$ where $V' = V \cup N$ and $E' = E \cup (N \times V)$. If $G$ has an Independent Set $S$ of size at least at least $k$ then $G'$ has a Triangle-Free set $S'$ of size at least $n+... 4 You can always satisfy at least half of clauses: for each variable$x$, find the number of clauses that contain$x$and the number of clauses that contain$\lnot x$. Select the one which satisfies the most clauses. Remove clauses containing$x$and$\lnot x$. Repeat for other variables. Since for each$x$we satisfy at least half of removed clauses, we ... 4 Unfortunately, I don't possess a copy of Sipser, so I will just define all my notation. Let$T_0,T_1,\ldots$an enumeration of all oracle Turing machines whose input is a word over some alphabet$\Sigma$. I will denote by$T_i^O(x)$the output of the execution of$T_i$on input$x$with oracle$O$, or$\bot$if the machine doesn't halt. We say that$T_i$(... 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 Let me explain how to solve this, leaving all details to you. Given an instance$(G,k)$of CLIQUE, we want to construct an equivalent instance of$\frac{n}{3}$-CLIQUE, say$G'$. Let us denote by$|G|$the number of vertices in$G$. There are several cases to consider: Case 1:$k = |G|/3$. In this case you can take$G' = G$. Case 2:$k > |G|/3$. In this ... 3 The number of k-tuples of vertices in a graph with$n$vertices are:$^nC_k$. You can iterate through each possible k-tuple and check in$O(k^2)$time whether the given k-tuple forms a clique. For any fixed natural$k$, the number$^nC_k$is$O(n^k)$, and hence you can check whether a graph has$k$-clique in$O(k^{2}.{^n}C_k)$; the problem would be in$P$. ... 3 Let$H$be the language of all Turing machines that halt on empty input. Clearly$H$is undecidable. Let$L = \{ (1,T) : T \in H \} \cup \{ (0,T) : T \not\in H \}$. Clearly$L$is undecidable. If$L$were decidable, then a Turing machine$M$for$L$would also imply the existence of a Turing machine$M'$that decides$H$.$M'$with input$T$simply ... 3 An NP-complete problem is in NP, by definition. No reduction needed. 3 Without loss of generality consider an instance$\langle S, t \rangle$of subset sum where$S$contains only positive integers and$t \ge 1$(zeros can be dropped from$S$, and the case$t=0$is trivial). Now build a new instance$\langle T, t' \rangle$of your generalized version of subset sum by choosing$T = \{ (t+1)x : x \in S \}$and$t'=t(t+1)$. If ... 3 No. The gamer will basically have to work out the SAT problem in their head. Think of any video game puzzle you've solved that wasn't easy. You probably solved it by working out a simpler version of the problem and then solving that. If you "complexify" SAT into a video game level, the best way to solve the video game level will be to simplify it ... 3 (For the below, I referred extensively to this github repo as well as private communication with @aozgaa) Languages can be represented as infinite-length bitstrings (ILB). We will use the two interchangeably. We will also represent strings meant to be inputs to TMs as integers, where a 1 bit in position$w$in an ILB$A$means that the$w$th string in$\...

3

I think the whole misunderstanding comes from an incorrect definition of TFNP. TFNP is for problems like factoring, where there is always a solution. Every integer has a prime factorization, so you don't have to make any restrictions on what inputs are allowed - i.e., every input string of bits represents a number that has a factorization. This is different ...

2

The answer by Draconis is wrong in "showing that the new problem is NP-hard." Reducing from something in NP to a new problem does not show NP-hardness. In particular, if a problem A is in P it is also in NP. Suppose there is a reduction from such a polynomial-time solvable A to some new problem B. Then, problem B still can be in P, and in this case ...

2

To show that Vertex Cover and 3SAT is "equivalent", you have to show that there is a 3SAT satisfaction if and only if there is a k vertex cover in the graph constructed in the reduction step. Assuming you are familiar with how the reduction is done, (if not ,refer to the document). Since you only asked about how this setup proves that if there exists a k-...

2

Suppose we are given a set of constraints of the form $b_i \oplus b_j = c$. We construct a graph with one vertex corresponding to each $b_i$. For each constraint of the form $b_i \oplus b_j = 1$, we add an edge $\{i,j\}$. For each constraint of the form $b_i \oplus b_j = 0$, we add a new vertex $x$, and two edges $\{i,x\},\{j,x\}$. We can think of a cut as ...

2

Showing that this your problem is in NP is easy. To show that your problem is NP-hard, reduce from PARTITION. The reduction simply chooses a large enough modulus $k$. Details left to you.

2

The problem is polynomial-time solvable. To avoid edge cases it is better to think that the job needs to be scheduled at time $0$ and that $c(0)=0$. Let $OPT[t,p]$ be the minimum amount of budget that needs to be spent in order to schedule the job in the first $t$ slots with an overall penalty of at most $p$ and with the additional constraint that the job ...

2

To show that $A$ is Turing-reducible to $B$ you need to prove the existence of a Turing Machine that is able to decide $A$ when given access to an oracle for $B$. In your specific case a possible Turing Machine $M$ takes as input a string $x \in \{0,1\}^*$ encoding the natural number $n$ (I'm assuming $0 \in \mathbb{N}$) in binary and operates as follows: ...

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

Sipser reduces $A_{\mathit{TM}}$ to $\mathit{HALT}_{\mathit{TM}}$. Since $A_{\mathit{TM}}$ is uncomputable, it follows that $\mathit{HALT}_{\mathit{TM}}$ has to be uncomputable. He is using the following general statement: If $A$ reduces to $B$ and $B$ is uncomputable, then so is $A$. You are right that this general statement itself is proved by ...

2

In the special case where $L=1$, this is the maximum independent set problem, which is NP-hard on general graphs. Therefore, your problem is NP-hard on general graphs as well. You could try to hope for an algorithm that is specific to the class of graphs you have (I think the maximum independent set can be computed efficiently in bipartite graphs, and grid ...

2

We will reduce from 3COL, which is the following problem: Given a graph, is it 3-colorable? Given a graph $G=(V,E)$, we construct a new graph $G'$ on $V \times \{1,2,3\}$, whose edges are $$\{((i,a),(j,a)) \mid (i,j) \in E, a \in [3]\} \cup \{((i,a),(i,b)) \mid i \in V, 1 \leq a < b \leq 3 \}.$$ In words, we take three copies of $G$, and connect all ...

2

There are multiple notions of "reduction." You've correctly described a many-one reduction of $HALT$ to $A_{TM}$. The reduction you've linked to (more specific link here) is instead a truth-table reduction. These are more general objects (so your result is stronger). Each is in turn subsumed by the much broader notion of Turing reduction. While many-one ...

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 Consider an instance of Halting problem$\langle M, x \rangle$. Construct a new Turing Machine which$M_x$which will accept the strings$0$,$00$,$000 \ldots 0^{2020}$if the machine$M$halts on the input$x$; and it will reject all other strings. Let$M_u$be the TM which accepts all the strings. Convince yourself that$|L(M_x) \cap L(M_u)|$will be ... 2 There are a few ways to approach this. You can use a counting argument to show that for every$A$there exists$B$such that$B\nleq_T A$. Let$L_A=\{B| B\le_T A\}$denote the set of all languages reducible to$A$. Show that$f:L_A\rightarrow \mathbb{N}$that maps languages$B\in L_A$to$n$such that$M_n$is a reduction from$B$to$A\$ is an injection, and ...

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