Non-Deterministic Space
Last edited: August 8, 2025Non-Deterministic Space is like Non-Deterministic Computation but now is space efficient.
requirements
We say \(A \in \text{NSPACE}\qty(s \qty(n))\) if \(\exists\) Non-deterministic Turing Machine \(M\) which decides \(A\) such that \(M\) always uses \(O\qty(s \qty(n))\) space.
additional information
See NL
Non-deterministic Turing Machine
Last edited: August 8, 2025We have multiple transitions for a state, symbol pair in non-deterministic TMs.
- the machine may proceed according to several possible transitions
- the machine accepts an input if there exists an accepting computation history for the machine on the string
Here’s the

basically a turing machine except the transition is a subset instead of a single transition.
\(L\) is in \(NP\) IFF there are polynomial-length proofs (“witnesses”) that can be decided efficiently for membership in \(L\)
There exists some constant \(k\) and a polynomial-time Turing-machine \(V\),
non-homogeneous linear differential equation
Last edited: August 8, 2025\begin{equation} y’ + ay = f(t) \end{equation}
The general solution for this would be
- any solution specifically which gives \(f(t)\), plus
- any homogeneous solutions
specifically:
\begin{equation} y = y_{p}(t) + y_{n}(t) \end{equation}
where the left is a particular solution, and the right is any homogeneous solution. We can do this because, say if we derivate it; the left derivative (the particular solution) gives \(f(t)\), and the right, because its homogeneous, gives 0.
Non-Intersecting Graphs (Single Order)
Last edited: August 8, 2025In this project, we aim to derive situations for the existence of a differential equation for when a family of functions do not intersect. We were able to derive a full solution for the result in linear equations, and we offer an exploration of a partial solution for non-linear cases.
Function Families
Fundamentally, function families are functions parameterized by some \(C\), which has the shape:
\begin{equation} y(x, \dots, c) = f(x, \dots)+c \end{equation}
Non-Linear ODE
Last edited: August 8, 2025Suppose we analyze first order non-linear system:
\begin{equation} x’ = F(t,x) \end{equation}
We can actually turn this into an autonomous system:
\begin{equation} x_0 = t \end{equation}
\begin{equation} x_0’ = 1 \end{equation}
meaning suddenly we have an autonomous system:
\begin{equation} \begin{cases} x_0’ = 1 \\ x_1’ = F(x_0, x_1) \end{cases} \end{equation}
General strategy:
- Find zeros of the right side (which are the stationary solutions)
- Analyze near-stationary solutions through eigenvalues of the linearized Jacobian matrix: if both eigenvalues are zero
- Away from stationary solutions: basically guessing
Three Examples that are Hopeless to Solve
Lotha-Volterra Prey-Predictor Equation
\begin{equation} \begin{cases} x_1’ = 2x_1-x_1x_2 \\ x_2’ = x_1x_2 - 3x_2 \end{cases} \end{equation}
