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 ...


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.


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