this is for holding javascript data
Vadim Kosoy added We_now_introduce_our_notion__.tex
about 8 years ago
Commit id: 4e38578fa95cae1a36522fc9f5d21dabbdf893dd
deletions | additions
diff --git a/We_now_introduce_our_notion__.tex b/We_now_introduce_our_notion__.tex
new file mode 100644
index 0000000..2df27db
--- /dev/null
+++ b/We_now_introduce_our_notion__.tex
...
We now introduce our notion of an "efficient" algorithm.
\begin{definition}
Fix $n \in \Nats$ and a growth space $\Gamma$ of type $(n,2)$. Given encoded sets $X$ and $Y$, a \emph{$\Gamma$-scheme of signature $X \rightarrow Y$} is a triple $(S,\R_S,\A_S)$ where $S: \Nats^n \times X \times \Words^2 \xrightarrow{alg} Y$, $\R_S: \Nats^2 \rightarrow \Nats$ and $\A_S: \Nats^2 \rightarrow \Words$ are s.t.
\begin{enumerate}[(i)]
\item There is a polynomial $p: \Nats^n \rightarrow \Nats$ s.t. for any $K \in \Nats^n$, $x \in X$ and $y \in \WordsLen{\R_S(K)}$, $T_S(K,x,y,\A_S(K)) \leq p(K)$.
\item $\R_S \times \Abs{\A_S} \in \Gamma$
\end{enumerate}
Abusing notation, we denote the $\Gamma$-scheme $(S,\R_S,\A_S)$ by $S$. $S^K(x,y,z)$ will denote $S(K,x,y,z)$, $S^K(x,y)$ will denote $S(K,x,y,\A_S(K))$ and $S^K(x)$ will denote a random variable which equals $S(K,x,y,a(K))$ for $y$ sampled from $U^{\R_S(K)}$. We think of $S$ as a randomized algorithm with advice where $y$ are the internal coin tosses and $\A_S$ is the advice.
We will use the notation $S: X \xrightarrow{\Gamma} Y$ to signify $S$ is a $\Gamma$-scheme of signature $X \rightarrow Y$.
\end{definition}
Instead of requiring the time complexity to be polynomial in $K$, we could have used a growth space of type $(n,3)$ which determines the allowed time complexity as well as the allowed randomization and advice. However, we make do without this generalization in the current work.
