[comp_complex] Solutions

  • From: David Friedman <dkf@xxxxxxxxxx>
  • To: <comp_complex@xxxxxxxxxxxxx>
  • Date: Tue, 6 Apr 2004 12:22:20 -0400 (EDT)

http://www.cs.jhu.edu/~dkf/assign_6_soln.pdf

Hints for the next assignment:

Problem 20:

1. Convert the boolean expression that represents that Pi_1, Pi_2, and
Pi_3 are false into 3CNF.

2. A smaller epsilon means a harder MAX3SAT (e.g. if
epsilon=1/100 then the machine only says true if between 100/101 and
101/101 of the clauses are true). The question asks you to find the
maximum epsilon such that it still can still satisfies the PCP definition.
To do this consider the worst case: what are the minimum fraction of
clauses that can be false when x is not an element of L.


Other related posts: