CS 21 Decidability and Tractability Winter 2024
Out: February 7
Due: February 14
Problem Set 4
Copyright By PowCoder代写 加微信 powcoder
Reminder: you are encouraged to work in groups of two or three; however you must turn in your own write-up and note with whom you worked. You may consult the course notes and the text (Sipser). The full honor code guidelines and collaboration policy can be found in the course syllabus.
Please attempt all problems. Please select one the last two problems to be graded completely (and indicate clearly which one); the other one will receive 1 point for a credible attempt. Please turn in your solutions via Gradescope, by 1pm on the due date.
1. [worth 6 pts] This problem concerns that language TILE, defined as follows. Informally, an instance is a collection of k tile types, together with a list of horizontally compatible pairs of tile types, and a list of vertically compatible pairs of tile types. An n × n tiling is a placement of tiles into an n × n grid, so that every pair of horizontally adjacent tiles is horizontally compatible, and every pair of vertically adjacent tiles is vertically compatible; in addition we require that the tile in the upper left corner is tile type 1. The language TILE consists of all those instances for which there exists an n × n tiling for all n ≥ 0.
Formally, the language TILE is the set of those tuples
⟨k,H ⊆[k]×[k],V ⊆[k]×[k]⟩
for which the following holds. For all n ≥ 1 there exists a function f : [n] × [n] → [k] for which:
• f(1,1)=1,and
• (f(x,y),f(x,y+1))∈H forall1≤x≤n,and1≤y≤n−1,and • (f(x,y),f(x+1,y))∈V forall1≤x≤n−1and1≤y≤n.
Here, [n] is shorthand for the set {1, 2, 3, . . . , n}. Prove that TILE is undecidable by giving a reduction from HALT (the complement of the language HALT). In other words, give a function R mapping instances of HALT to instances of TILE, with the property that R(⟨M,w⟩) is in the language TILE if and only if ⟨M, w⟩ is in the language HALT. Hint: it will be helpful to “name” some of your tiles with triplets of symbols.
2. Two graphs G1 = (V1, E1) and G2 = (V2, E2) are isomorphic if there is a bijection f : V1 → V2 suchthat(u,v)∈E1 ⇔(f(u),f(v))∈E2. ForagivengraphH,definethefollowinglanguage:
containsH = {G : G contains a subgraph isomorphic to H}.
Here by “subgraph” we mean a subset of G’s vertices together with all of G’s edges on that subset of vertices – often called an “induced subgraph.” Prove that for every H, CONTAINSH is in P.
3. Show that the following problem is in P:
() unary subset sum = (1B,x1,x2,…,xn) : ∃ a multiset I of [n] for which Xxi = B .
Here the xi are all positive integers, as is B, and [n] is shorthand for the set {1, 2, 3, . . . , n}. The notation 1B means a string of B ones, which is the representation of B in unary. Hint: solve the problem for all B′ ≤ B.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com