According to the Cook-Levin theorem, VERTEX COVER ≤p SAT. It is interesting to show such results directly, without refer

[answerhappygod]

According to the Cook-Levin theorem, VERTEX COVER ≤p SAT. It is
interesting to show such results directly, without reference to
Turing machines.

According To The Cook Levin Theorem Vertex Cover P Sat It Is Interesting To Show Such Results Directly Without Refer 1 (62.99 KiB) Viewed 33 times

3. According to the Cook-Levin theorem, VERTEX COVER <p SAT. It is interesting to show such results directly, without reference to Turing machines. a) Show there is a compact formula T(n, k) that evaluates to 1 precisely when k out of ₁,...,n are assigned the value 1. "Compact" means that its length is bounded by a polynomial in n. b) Let (G, k) be an instance of VERTEX COVER. Give a Boolean formula that is satisfiable iff G has a vertex cover using <k vertices, and argue that the function that takes (G, k) to the formula is computable in polynomial time. [Hint: your formula should have a variable for each vertex in G, and make use of T(n, k) from a).]