Vadim Kosoy edited We_now_introduce_our_notion__.tex  about 8 years ago

Commit id: 5f8076279e83a18eacfc11f2a19dcddc0cafeb63

deletions | additions      

       

\begin{definition}  Fix $n \in \Nats$ and $\Gamma=(\Gamma_{\mathfrak{R}}$, $\Gamma_{\mathfrak{A}})$ a pair of  growth spaces$\Gamma_{\mathfrak{R}}$, $\Gamma_{\mathfrak{A}}$  of rank $n$. Given encoded sets $X$ and $Y$, a \emph{$(\Gamma_{\mathfrak{R}}, \Gamma_{\mathfrak{A}})$-scheme \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 \xrightarrow{alg} \Nats$ and $\A_S: \Nats^2 \rightarrow \Words$ are s.t. \begin{enumerate}[(i)] 

\end{enumerate}  Abusing notation, we denote the $(\Gamma_{\mathfrak{R}}, \Gamma_{\mathfrak{A}})$-scheme $\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_{\mathfrak{R}}, \Gamma_{\mathfrak{A}}} \xrightarrow{\Gamma}  Y$ to signify $S$ is a $(\Gamma_{\mathfrak{R}}, \Gamma_{\mathfrak{A}})$-scheme $\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 3rd third  growth space which determines the allowed time complexity. However, we make do without this generalization in the current work.