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
