HW#2 --- last modified March 02 2019 21:31:07..
Solution set.
Due date: Oct 2
Files to be submitted:
Hw2.tex
HornChecker.zip
Purpose: To be able to classify problems as decidable or undecidable.
To gain some understanding of circuits.
Related Course Outcomes:
Problems (1) and (2) concerns Learning Outcome (1): Exhibit a
simulation of one machine model with another.
Problem (3) is connected to leaning outcome (2) Give a minimal
classification of the complexity of a computational problem as being in one of the class ALogTime, L, P, NP,
coNP, some level of the polynomial hierarchy, PSPACE, E, EXPTIME, decidable, undecidable. In this case, we are
concerned about decidable versus undecidable.
The coding part of the assignment is connected to learning outcome (2) mentioned above as well as connected to
the background needed for learning outcome (6) Explain at least one circuit lower bound technique such as
Razborov's techniques for monotone circuits.
Specification:
1. Consider the model of nondeterminism where the number of possible transitions one
has reading the same symbol in the same state is at most two. Show this model
can simulate the usual model of nondeterminism with at most a polynomial time slow down.
2. Identify the natural numbers with binary strings in a reasonable way. Consider the following
functions from tuples of natural numbers to naturals: 0 -- the function
which on any input outputs 0. 1 -- the function which on any input outputs 1. x + y which on
input a pair x,y outputs their sum. x * y -- which on input a pair x,y outputs their product.
2x -- which on input x outputs 1 followed by x zero's. (i) Show that each of these functions
is computable by a Turing Machine. (ii) Show that if f(x1,...,xi-1,xi,xi+1..xk)
and g(y1,..ym) are functions computable by a
Turing machine, then so is the composition f(x1,...,xi-1,g(y1,..ym),xi+1..xk).
(iii) Given two functions g(x1,...xk) and h(y,z, x1,...xk) let f be the unique function such that
f(0,x1,...xk) = g(x1,...xk)
f(n+1, x1,...xk) = h(n, f(n, x1,...xk), x1,...xk)
Here f is said to be defined by primitive recursion from g and h. Show that if f is defined by primitive recursion form g and h, and g and h
are computable, then f is computable. (iv) Give a function f from the tuples of naturals to naturals, define μ y f(y,
x1,...xk)=z
to be the least y such that f(y, x1,...xk) = z, if such a y exists and is undefined otherwise. Functions which are not
defined on
all inputs are called partial functions. Suppose f is computable
show that there is a Turing machine which computes a y satisfying μ y f(y, x1,...xk) if such a y exists and runs forever
otherwise. (v) The μ-recursive functions are the smallest class of partial functions which contain the functions of part (i) and which are closed
under composition, primitive recursion, and the μ-operator of part (iv). Note my definition is a variation on the standard one. We have just argued
that such functions can be simulated on a Turing machine. Now let U(x,y) be a fixed universal Turing Machine with inputs x and y. This machine computes
some partial function. Show how to represent this partial
function as a μ-recursive function.
3. Do problem 3.4.1 out of the book.
For the coding part of the assignment, I would like you to implement the polynomial time algorithm from class for checking if a set of Horn
clauses is satisfiable. I will assume the Horn clauses are stored in some file with one
clause per line. A line has the format int:int,int,int,...,int.
For example:
21:1,45,2
This represent the Horn clause x21 OR NOT(x1) OR NOT(x45) OR NOT(x2). If a line begins
with a : then it is assumed all variables in the clause are negated. I will test your program on the command line with a line like:
java HornChecker file.txt
Here HornChecker should be the name of your program and file.txt will be my file of Horn clauses. You program should output `yes' if the set of
clauses is satisfiable and `no' otherwise. It should do its calculations based on the
algorithm from class.
Point Breakdown
LaTeX file compiles and Java Coding guidelines followed |
1pt
|
Problem 1 above |
1pt
|
Problem 2 (each part worth .6 pts) |
3pts
|
Problem 3 |
2pts
|
Program implements Horn algorithm from class |
2pts
|
Program passes all test files |
1pt
|
Total | 10pts |
|