coNP is the set:

\begin{equation} \text{coNP}= \qty {\neg L \mid L \in NP} \end{equation}

“\(L\) is in coNP if there exists a poly-time verifier for the “no” instances of this language”. Formally:

\begin{equation} L \in \text{coNP} \Leftrightarrow \exists \text{polytime} V s.t. x \in L: \exists w \in \qty {0,1}^{\text{poly}\qty(x)}, V\qty(x,w) = 1 \end{equation}

Some coNP stuff: UNSAT, NOT-3COL, etc.

\(P \subseteq coNP\)

Because we just invert the judgments after running \(P\) to get the whole set.

constructor theory deals with “constructors”, a general type of computer.

constructor theory can give us a theory of the universal quantum constructor by expanding upon quantum information theory. It allows us to unify quantum and classical information by simply defining operations in terms of counterfactuals exclusively: that a space is entirely defined by what’s possible and what’s not possible.

According to constructor theory, fundamental laws are not dynamical laws instead are boundary conditions. We can take the boundary conditions to form the most general set of initial conditions.

We use CFGs to highlight the recursive structure in expressions.

A CFG consists of

• Non-Recursed Terminals (if, else, etc.) \(T\)
• Non-Terminals (expr, stmt, etc.) \(N\)
• Start symbol (i.e., program) \(S \in N\)
• Set of productions

generative semantics

Let \(G\) be an CFG with start symbol \(S\); the language of \(G\) is…

\begin{equation} \qty {a_1, \dots, a_{n} | S \to^{*} a_{1}, a_{n}} \end{equation}

with each \(a_{j}, \forall j\) being terminals.

That is, the “language of a CFG” is just the set of languages that could be produced by as many moves as needed until we obtain the output.