Computational Complexity Theory
Last edited: August 8, 2025Computational Task
Last edited: August 8, 2025Decision problems
- a decision problem: \(\Sigma^{*} \to \qty {\text{no}, \text{yes}}\)
- we often associate the “yes” instances of this decision problem as a \(L \subseteq \Sigma^{*}\) language
“Given boolean formula \(\varphi\), accept IFF \(\varphi\) is SAT”
Function problems
Give me a particular case of:
\begin{equation} f(w) : \Sigma^{*} \to \Sigma^{*} \end{equation}
note that there is a unique answer.
“Give a formula \(\varphi\), output lex first satisfying assignments/number of satisfying assignments”
computer number system
Last edited: August 8, 2025bit
A computer is built out of binary gates:
So, having voltage into \(B\) allows current to pass through between \(S\) and \(D\), it could be on/off.
byte
Accumulation of \(8\) bits
Computer memory is a large array of bytes. It is only BYTE ADDRESSABLE: you can’t address a bit in isolation.
bases
Generate, each base uses digits \(0\) to \(base-1\).
We prefix 0x to represent hexadecimal, and 0b to represent binary.
Computer Systems Index
Last edited: August 8, 2025Notes on CS 107, C, MIPS, and computational systems.
Lectures
- SU-CS107 SEP272023
- SU-CS107 SEP292023
- SU-CS107 OCT022023
- SU-CS107 OCT032023
- SU-CS107 OCT042023
- SU-CS107 OCT062023
- SU-CS107 OCT092023
- SU-CS107 OCT112023
- SU-CS107 OCT132023
- SU-CS107 OCT182023
- SU-CS107 OCT202023
- SU-CS107 OCT232023
- SU-CS107 OCT252023
- SU-CS107 OCT272023
- SU-CS107 NOV102023
- SU-CS107 NOV132023
- SU-CS107 DEC012023
Worksheets
conceptual grammar
Last edited: August 8, 2025conceptual grammar is the proposed universal grammar which connects semantic primes. In theory, this grammar is universal across languages.
There are three main categories of conceptual grammars:
- Combinatorics (connecting one idea to another)
- Account of valancies? #what
- Propositional complementation (location “something that happen in this place”