NFA is a relaxation of DFA, but which is allowed to make non-deterministic “verified guesses”.

this is basically a DFA, but our new machine accepts a string if there exists some path that reaches some accept state from some start state.

at each state, we can have any number of out arrows for some letter \(\sigma \in \Sigma\), including for the empty string \(\varepsilon\). meaning we can move between states without doing anything.

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

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\),

\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.

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}