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}

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}

“Chaotic Dynamics” Because the word is sadly nonlinear.

motivating non-linearity

\begin{equation} \dv t \mqty(x \\ y) = f\qty(\mqty(x\\y)) \end{equation}

This function is a function from \(f: \mathbb{R}^{2}\to \mathbb{R}^{2}\). All the work on Second-Order Linear Differential Equations, has told us that the above system can serve as a “linearization” of a second order differential equation that looks like the follows:

\begin{equation} \dv t \mqty(x \\y) = A \mqty(x \\ y) +b \end{equation}