\begin{equation} \text{UNSAT} = \qty {\phi : \text{all assignment make $\phi$ false}} \end{equation}

Equivalently, we have:

\begin{equation} \text{UNSAT} = \neg \text{SAT} \end{equation}

NP = coNP IFF UNSAT is in NP

\begin{equation} \text{NP} = \text{coNP} \Leftrightarrow \text{UNSAT} \in \text{NP} \end{equation}

\(\Rightarrow\)

Because \(\text{UNSAT} \in \text{coNP}\), and we hypothesize NP = coNP, so \(\text{UNSAT} \in \text{NP}\)

\(\Leftarrow\)

Suppose UNSAT in NP, we desire that \(\text{coNP} = NP\). Let \(L \in \text{coNP}\),so \(\neg L \in \text{NP}\), since SAT is NP-complete, we can write that \(L \leq_{p} \text{SAT}\). Equivalently, we have \(L \leq_{p} \neg \text{SAT} = \text{UNSAT}\). Since \(\text{UNSAT} \in \text{coNP}\), we have \(L \in \text{NP}\).

A matrix is upper-triangular if the entries below the diagonal are \(0\):

\begin{equation} \mqty(\lambda_{1} & & * \\ & \ddots & \\ 0 & & \lambda_{n}) \end{equation}

properties of upper-triangular matrix

Suppose \(T \in \mathcal{L}(V)\), and \(v_1 … v_{n}\) is a basis of \(V\). Then:

1. the matrix of \(T\) w.r.t. \(v_1 … v_{n}\) is upper-triangular
2. \(Tv_{j} \in span(v_1 \dots v_{j})\) for each \(v_{j}\)
3. \(span(v_{1}, … v_{j})\) is invariant under \(T\) for each \(v_{j}\)

\(1 \implies 2\)

Recall that our matrix \(A=\mathcal{M}(T)\) is upper-triangular. So, for any \(v_{j}\) sent through \(A\), it will be multiplied to the $j$-th column vector of the matrix. Now, that $j$-th column has \(0\) for rows \(j+1 … n\), meaning that only through a linear combination of the first \(j\) vectors we can construct \(T v_{j}\). Hence, \(Tv_{j} \in span(v_1 … v_{j})\)

• Investment: Paid for 50% of war bonds
• Production: ships, tanks, airplanes, etc. — encourages production
• Conservation: 5% of the world’s population production, 50% of the world’s manufactured goods — rationing, grow goods, etc.

USAYPT or USIYPT is a physics research competition ran by Greg Jacobs.

2022

My own work doc for the 2022 Tuning Forks problem is here.

General Tips

• When in doubt, ask about error prop
• ANSWER THE RESEARCH QUESTION (elevator)
• Convey that you understand basics via presentation
• Have intuition regarding phenomenon
• Be able to explain every formula from first principles
• Order of magnitude and dimension analysis
• Have clear variance in parameters (what did you vary and why)
• What does the intercepts mean on graphs?
• “Don’t be obtuse”
• Connect to simple physics terms
• Explanations needs to be simple
• Engage discussion

User Experience is the