Homework 3 of cs 6382
(No late homework will be accepted)
1. Let x and y be Boolean variables, and u = ¬max(x, y) and v = ¬min(x, y). Show that 6= x
can be represented monotonically from x, y, u, v (with only AND and OR operations).
2. Show that if the maximum flow problem can be solved by NC-circuits, then every problem
in P can be solved by NC-circuits. Also, show that if the linear programming (i.e., maximize
a linear function subject to linear inequality constraints) can be solved by NC-circuits, then
every problem in P can be solved in NC-circuits.
3. Show that the following problem is #P -complete: How many different variable assignments
will satisfy a given 2CNF formula?
4. Consider a system with a graph structure. Each node has working probability p. The system
fails if and only if there exists an edge whose endpoints both fail. Show that computing the
reliability of the system is a #P -hard problem.
5. Show that the following problem is #P -complete: Given a directed graph G and two nodes
s and t, count how many subgraphs of G containing a path from s to t.
1