2023年11月25日

图灵机代写｜Turing machine homework2

本次美国代写是一个图灵机相关的assignment

Transitivity of Reductions

Problem 1. Let f; g; h : f0; 1g∗ ! f0; 1g be functions such that f ≤ g and g ≤ h; prove that
f ≤ h. Deduce that if computing f is NP−hard then so is computing g and h. Similarly, deduce
that if h can be computed in polynomial time, then so can f and g.

Some More NP−complete Problems

Problem 2. Prove that three of the following languages are NP−hard.

• Rules: For each language you choose, you must give a polynomial time reduction from a known
NP−complete language. These can include any of the languages we proved NP−complete
in class, as well as any language in the following list (other than the language itself; i.e.,
you cannot prove L NP−complete by proving L ≤ L).

• QUAD-EQ = f(’1; : : : ; ’m) satisfiable 3-local quadratic equations over n boolean variablesg, where
a 3-local quadratic equation over the variables x1; : : : ; xn has the form
xixj − xk ≡ 1(mod 2)

for some i; j; k 2 f1; : : : ; ng. We say that a sequence of 3-local quadratic equation over
n boolean variables is satisfiable if there exists a 0/1 assignment to each of the variables
x1; : : : ; xn which simultaneously satisfies all the equations.

Hint: Reduce from CIRCUIT − SAT; you may assume circuits can be constructed entirely of
NAND gates.

• dHAMPATH = fG directed graph : 9 Hamiltonian cycleg, where a Hamiltonian cycle in a
graph G = (V; E) is a list of vertices v0; v1; : : : ; vn such that v0 = vn and each other vertex
in V appears exactly once in the list and moreover (vi−1; vi) 2 E for all i = 1; 2; : : : ; n.

• HAMPATH = fG undirected graph : 9 Hamiltonian cycleg, where a Hamiltonian cycle in a
graph G = (V; E) is a list of vertices v0; v1; : : : ; vn such that v0 = vn and each other vertex
in V appears exactly once in the list and moreover (vi−1; vi) 2 E for all i = 1; 2; : : : ; n.