# Tag Info

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 ... 1 welcome to the site :) I assume you already know that the Halting problem$L_H$is undecidable (as it is usually the first specific undecidable language students learn of). So, let us try and find a reduction$L_H \leq EQ$. We want to know whether some given TM$M$halts given the input word$w$by transforming the pair$\langle M, w \rangle$to some$EQ$-... 1 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 ... 1 If there is a finite number of exceptions to the Goldbach conjecture then it is still solvable in linear time. Note that there is a non-zero probability that the Goldbach conjecture is false. Heuristically, the probability for an infinite number of exceptions is zero. 1 Interpretation (i) is correct: "$A$is at least as hard as$B$" means that$A$is as hard as or strictly harder than$B$. (Think about numbers: "$a$is at least as big as$b$" means "$a=b$or$a>b$.") Note that not only does "$A$is at least as hard as$B$" rule out$A$being strictly weaker than$B$, it also rules ... 1 If$L_2 \neq \Sigma^*$and$L_2 \neq \emptyset$then$L_1 \in R$and$L_2 \in RE$implies$L_1 \le_m L_2$. Let$T$be a Turing machine that decides$L_1$. Let$a,b \in \Sigma^*$such that$a \in L_2$and$b \not\in L_2$. For$x \in \Sigma^*$, define$\phi(x) = \begin{cases} a & \text{ if $T(x)$ accepts }\\ b & \text{ if $T(x)$ rejects } \end{cases}$. ... 1 The language$L^*$consists of all Turing machines$M$which either eventually halt or repeat a configuration. For each machine$M\$, by simulating the machine you can easily observe that one of these possibilities has happened.