_index.org

Non-Deterministic Space

Last edited: August 8, 2025

Non-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, 2025

We have multiple transitions for a state, symbol pair in non-deterministic TMs.

  1. the machine may proceed according to several possible transitions
  2. 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

  1. any solution specifically which gives \(f(t)\), plus
  2. 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, 2025

In 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, 2025

Suppose 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:

  1. Find zeros of the right side (which are the stationary solutions)
  2. Analyze near-stationary solutions through eigenvalues of the linearized Jacobian matrix: if both eigenvalues are zero
  3. 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}