HW5.org

HW 5: Lambda Calculi and Time Complexity

Problem 1

Consider a binary tree that is either

• a leaf
• or a node with two other binary trees as its descendants

You should

1. give this datatype a church encoding in the untyped lambda calculus
2. write a function that returns true if its argument is a node and false if its a leaf
3. write a function that counts the number of nodes in a tree (for this purpose just assume that numbers exist as a datatype and are equipped with binary addition)

Problem 2

(from Sipser) Let Double-SAT be the language { φ | φ has at least two satisfying assignments }. Show, by polynomial time reduction, that Double-SAT is NP-complete.

Problem 3

(from Sipser) Show that, if P = NP, then every language A ∈ P that is not trivial (either \varempty or Σ^*) is NP-complete.