Week 9

• isn’t \(P^{\text{SAT}}\) just \(\text{SAT}\) with more steps? i.e., because an “oracle” for \(\text{SAT}\) is just a system that checks SAT, and we know that can be done in P no it isn’t because checking requires a witness
• can we use CLIQUE in pset

Week 8

• ask Omer to go over subset sum

Week 7

• so in NP, “nondeterministically guess” happens in order-1 time for all possible choices?

Week 6

• interpreter arguments: why is that changing \(K(x)\) up to a constant? i.e. for instance doesn’t the choice of \(K_{p}(x)\) matter?
• Godel’s consistency: why does the

imply that \(\neg S_{G,\varepsilon}\) is true?

a quotient group is a group which is the product of mapping things out.

subgroups

The set of integers \(\mathbb{Z}\) is obviously a group. You can show it to yourself that multiples of any number in the group is a subgroup of that group.

For instance:

\(3 \mathbb{Z}\), the set \(\{\dots -6, -3, 0, 3, 6, \dots\}\) is a subgroup

actual quotient groups

We can use the subgroup above to mask out a group. The resulting product is NOT a subgroup, but its a new group with individual elements being subsets of our original group.

The quotient map \(\pi\) is the Linear Map \(V \to V / U\) such that:

\begin{equation} \pi(v) = v+U \end{equation}

for \(v \in V\).

I.e.: the quotient map is affine subsetification map given a vector.

Suppose \(T \in \mathcal{L}(V)\), and \(U \subset V\), an invariant subspace under \(T\). Then:

\begin{equation} (T / U)(v+U) = Tv+U, \forall v \in V \end{equation}

where \(T / U \in \mathcal{L}(V / U)\)

“if you can operator on \(V\), you can operator on \(V / U\) in the same way.” Yes I just verbed operator.

quotient operator is well-defined

Why is this not possible for any subspace of \(V\)? This is because we need \(T\) to preserve the exact structure of the subspace we are quotienting out by; otherwise our affine subset maybe squished to various unexpected places. The technical way to show that this is well-defined leverages the property of two affine subsets being equal:

A quotient space is the set of all affine subsets of \(V\) parallel to some subspace \(U\). This should be reminiscent of quotient groups.

constituents

• vector space \(V\)
• a subspace \(U \subset V\)

requirements

\begin{equation} V / U = \{v+U : v \in V \} \end{equation}

additional information

operations on quotient space

Addition and scalar multiplication on the quotient space is defined in the expected way:

given \((v+U), (w+U) \in V / U\), and \(\lambda \in \mathbb{F}\):

\begin{equation} \begin{cases} (v+U) + (w+U) = ((v+w)+U) \\ \lambda (v+U) = ((\lambda v)+U) \end{cases} \end{equation}