*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.

- » [comp_complex] Solutions
- » [comp_complex] Solutions
- » [comp_complex] Solutions
- » [comp_complex] Solutions
- » [comp_complex] Solutions
- » [comp_complex] Solutions
- » [comp_complex] Solutions
- » [comp_complex] Re: Solutions
- » [comp_complex] Solutions