# Search vs decision

The P vs NP question is about decision problems. In this exercise, you will show that P=NP implies that certain search problems have efficient algorithms.

Show that if P=NP then there exists a polynomial-time algorithm that given a 3CNF formula $$\varphi$$ outputs a satisfying assignment for $$\varphi$$ if such an assignment exists.

# Random subset sum

The set $$\{0,1\}$$ with addition and multiplication modulo 2 forms a finite field, denoted $$\bbF_2$$. The set $$\{0,1\}^n$$ with component-wise addition and scalar multiplication forms a vector space over this field, denoted $$\bbF^2$$. Just like for vector spaces over the reals, we can use matrices with their algebraic operations to describe linear maps on $$\bbF_2^n$$.

Show the following facts:

1. Let $$x,y\in \bbF_2^n$$ with $$x\neq y$$. Then, $\Pr_{r\in \bbF_2^n}\biggl\{ r^T x \neq r^T y \biggr\} =1/2\,.$

2. Let $$A\in \bbF_2^{n\times n}$$ be an invertible matrix and let $$y\in \bbF_2^n$$. Then, $\Pr_{x\in\bbF_2^n}\biggl\{ A x = y \biggr\} = 2^{-n}\,.$

3. Let $$x,y\in \bbF_2^n$$ with $$x\neq 0$$. Then, $\Pr_{A \in \bbF_{2}^{n\times n}} \biggl\{ A x = y \biggr\} = 2^{-n}\,.$

# Gap preserving reduction for independent set

In the lecture on 2/9, we sketched a gap preserving reduction from 3Sat to independent set. This exercise asks you to fill in the details for the proof sketch of the lemma.

1. Describe the polynomial-time function $$f$$ that maps every max3sat instance $$\varphi$$ to independent set instance $$G$$.
2. Describe how every assignment $$x$$ to the max3sat instance $$\varphi$$ corresponds to an independent set $$S$$ in $$G$$.
3. Describe how every independent set $$S$$ in $$G$$ corresponds to an assignment $$x$$ for $$\varphi$$.