4

Start with $5|E(G)|$ variables $x_{e,i}$, one for each $e \in E(G)$ and $i \in \{1,2,3,4,5\}$. Intuitively $x_{e,i}$ means that edge $e$ is colored with color $i$. A CNF formula $\phi$ can be obtained by the logical and of the following sub-formulas. Each edge must have exactly one color: At least one color, for each $e \in E(G)$: $(x_{e,1} \vee x_{e,2} \...


3

Let us actually prove more: If $L$ is a language and $L \not\in \mathsf{R}$, then $L \not\le_\mathrm{T} L'$ for any $L' \in \mathsf{R}$. (Here, $\le_\mathrm{T}$ indicates a Turing reduction; this is synonymous with your notion of a "computability" reduction.) In other words, $\mathsf{R}$ is closed under Turing reductions. Suppose towards a contradiction ...


2

Is that proof correct? Let's assume f is computable. Then I can show a TM which solves halting problem, actually even more - a TM which prints all halting TMs of given size. This TM works as following: Using blackbox for f, calculate f(n) Iterate through ALL possible TMs of input alphabet {0, 1}, states {0, 1..., n}, work alphabet {_, 0, 1, .... n} ...


2

My confusion is, [when proving that TSP is NP-hard by reduction from HAM-CYCLE] why don't we try to show that for each instance of TSP, there exists a corresponding instance of HAM−CYCLE. Because it doesn't matter. Being able to solve TSP allows you to solve HAM-CYCLE. The fact that it also allows you to do some other stuff (solve the TSP instances that don'...


2

Apparently, you are expecting the reduction between any two $\mathsf{NP}$-complete problems $X$ and $Y$ to be a one-to-one map (e.g., a bijection). The idea of a reduction, however, is irrelevant to having instances "correspond" to others. What reductions do give us is a hardness relation between problems (and not between individual instances). If $A$ and $B$...


2

You explain how to convert a ZPP machine to a BPP machine. This means that if a problem is in ZPP, then it is also in BPP. In other words, ZPP is contained in BPP.


1

The result from Buhrman et al. is about EXP rather than EXPSPACE. Note that Theorem 3.1 from Fortnow's survey is taken from the very same paper of Buhrman et al.


1

The trick to reducing any NP problem to SAT is 1) writing a subroutine that checks the polynomially-sized certificate, 2) converting that routine to a circuit, and 3) flattening the circuit to CNF using the usual methods. For example, to convert integer factorization to SAT, you would write a routine that multiplies two $n$-bit multipliers producing a 2$n$-...


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