  This Paper defines and explores solution to the problem of \emph{Inversion of
a finite Sequence} over the binary field, that of finding a prefix element of
the sequence which confirms with a \emph{Recurrence Relation} (RR) rule defined
by a polynomial and satisfied by the sequence. The minimum number of variables
(order) in a polynomial of a fixed degree defining RRs is termed as the
\emph{Polynomial Complexity} of the sequence at that degree, while the minimum
number of variables of such polynomials at a fixed degree which also result in
a unique prefix to the sequence and maximum rank of the matrix of evaluation of
its monomials, is called \emph{Polynomial Complexity of Inversion} at the
chosen degree. Solutions of this problems discovers solutions to the problem of
\emph{Local Inversion} of a map $F:\ftwo^n\rightarrow\ftwo^n$ at a point $y$ in
$\ftwo^n$, that of solving for $x$ in $\ftwo^n$ from the equation $y=F(x)$.
Local inversion of maps has important applications which provide value to this
theory. In previous work it was shown that minimal order \emph{Linear
Recurrence Relations} (LRR) satisfied by the sequence known as the \emph{Linear
Complexity} (LC) of the sequence, gives a unique solution to the inversion when
the sequence is a part of a periodic sequence. This paper explores extension of
this theory for solving the inversion problem by considering \emph{Non-linear
Recurrence Relations} defined by a polynomials of a fixed degree $>1$ and
satisfied by the sequence. The minimal order of polynomials satisfied by a
sequence is well known as non-linear complexity (defining a Feedback Shift
Register of smallest order which determines the sequences by RRs) and called as
\emph{Maximal Order Complexity} (MOC) of the sequence. However unlike the LC
there is no unique polynomial recurrence relation at any degree.
