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.

Used: IBM/OS360

contiguous allocation puts the files and metadata together, and implements a Explicit Free List Allocator across the file.

benefits

• simple

problems

• external fragmentation: little pockets of data is everywhere
• editing: hard to grow files

Consider:

we can consider this as two parts

• the computation of x = e1
• and the continuation e2

it essentially create statement labels:

such that:

• \(k_0 = \lambda w . k_1 e\)
• \(k_1 = \lambda x . k_2 e’\)
• \(k_2 = \lambda y . k_3 (x+y)\)
• \(k_3 = \lambda z . z\)

why

• we can make the order of evaluatinos explicit
• we give a name to each intermediate value
• we name every step of the computation

it is important in language implementation (where ever intermediate result is named); but we can also make continuation available as program value.