Graph Isomorphism is in NP
Last edited: August 8, 2025Recall the definition of graph : if you can relabel \(G\) to get \(G’\), that they are the same up to relabling.
\begin{equation} \text{GISO} = \qty {\langle G,G’ \rangle \mid G \cong G’} \end{equation}
Because the prover can just give the relabeling.
gravitational entanglement
Last edited: August 8, 2025Using constructor theory to test whether or not gravity in quantum theory is just entanglement.
This solves problem with gravity.
gravitational potential energy
Last edited: August 8, 2025Great Depression
Last edited: August 8, 2025The Great Depression is a period of time of American depression.
greatest common divisor
Last edited: August 8, 2025Let \(a,b \in \mathbb{Z}\), not both zero. \(\gcd (a,b)\) is the greatest value \(d\) such that \(d|a\), \(d|b\).
greatest common divisor is a linear combination
We can write \(\gcd (a,b) = as+bt\) for some \(s,t \in \mathbb{Z}\).
Let us define:
\begin{equation} S = \{am + bn: m,n \in \mathbb{Z}, am+bn > 0\} \end{equation}
We will first check that \(S\) is non-empty. To do so, let \(a\) be negative and \(b\) be positive. Then, set \(m = -1\), \(n = 1\). We can see that \(am + bn > 0\), satisfying the conditions of the set. In a similar manner, we can demonstrate that regardless of the choice of \(a, b\), \(S\) is non-empty.