## 1 Introduction: Problem Setting
### Computational Complexity of Algorithms
The computational problem can be considered as a mapping of function \(f:\{[0,1]^{d}\rightarrow\mathbf{R}\}\) to \(\mathbf{R}\): \(S(f):f\rightarrow\mathbf{R}\), where \(S(f)=\int_{U^{d}}f(\mathrm{x})d\mathrm{x}\) and \(f\in F_{0}\subset C(U^{d})\). We denote by \(S\) the solution operator. The elements of \(F_{0}\) constitute the input data for which the problem must be solved; specifically, for any \(f\in F_{0},S(f)\). In certain instances, there is interest in cases where the integrand \(f\) possesses higher regularity. This frequently occurs in practical computations, where \(f\) tends to be smooth and have bounded high-order derivatives. Under these circumstances, it is advantageous to exploit this smoothness. To accomplish this, we introduce the functional class \(F_{0}\), defined as  
\[F_{0}\equiv\mathbf{W}^{k}(\|f\|;U^{d}).\]  
Here, \(U^{d}\) denotes the domain of interest, and \(\mathbf{W}^{k}(\|f\|;U^{d})\) refers to the Sobolev space of functions on \(U^{d}\) with up to \(k\)-th order weak derivatives. The notation \(\|f\|_{U^{d}}\) symbolizes the norm associated with the Sobolev space \(\mathbf{W}^{k}\). By defining \(F_{0}\) in this fashion, we can effectively capture the smoothness characteristics of the function \(f\), thereby potentially enhancing the precision and computational efficiency of numerical methods designed for such smooth integrands. **Definition 1**. : _Let \(d\) and \(k\) be integers, \(d,k\geq 1\). We consider the class \(\mathbf{W}^{k}(\|f\|;U^{d})\) (sometimes abbreviated to \(\mathbf{W}^{k}\)) of real functions \(f\) defined over the unit cube \(U^{d}=[0,1]^{d}\), possessing all the partial derivatives \(\frac{\partial^{d}f(\mathrm{x})}{\partial x_{1}^{\alpha_{1}}\cdots \partial x_{d}^{\alpha_{d}}},\ \ \alpha_{1}+\cdots+\alpha_{d}=r\leq k\), which are continuous when \(r<k\) and bounded in \(\sup\) norm when \(r=k\). The seminorm \(\|\cdot\|\) on \(\mathbf{W}^{k}\) is defined as_  
\[\|f\|=\sup\Bigg{\{}\Bigg{|}\frac{\partial^{k}f(\mathrm{x})}{\partial x_{1}^{ \alpha_{1}}\cdots\partial x_{d}^{\alpha_{d}}}\Bigg{|},\ \ \alpha_{1}+\cdots+\alpha_{d}=k,\ \ \mathrm{x}\equiv(x_{1},...,x_{d})\in U^{d} \Bigg{\}}.\]  
We keep the seminorm \(\|f\|\) in the notation for the functional class \(\mathbf{W}^{k}(\|f\|;U^{d})\) since it is important for our further consideration. We call a _quadrature formula_ any expression of the form \[A^{D}(f,n)=\sum_{i=1}^{n}c_{i}f(\mathbf{x}^{(i)}),\]  
which approximates the value of the integral \(S(f)\). The real numbers \(c_{i}\in\mathbf{R}\) are called weights and the \(d\) dimensional points \(\mathbf{x}^{(i)}\in U^{d}\) are called nodes. It is clear that, for fixed weights \(c_{i}\) and nodes \(\mathbf{x}^{(i)}\equiv(x_{i,1},\ldots,x_{i,d})\), the quadrature formula \(A^{D}(f,n)\) may be used to define an algorithm with an integration error \(err(f,A^{D})\equiv\int_{U^{d}}f(\mathbf{x})d\mathbf{x}-A^{D}(f,n)\). We call a _randomized quadrature formula_ any formula of the following kind: \(A^{R}(f,n)=\sum_{i=1}^{n}\sigma_{i}f(\mathcal{E}^{(i)})\), where \(\sigma_{i}\) and \(\mathcal{E}^{(i)}\) are random weights and nodes, respectively. The algorithm \(A^{R}(f,n)\) belongs to the randomized class (Monte Carlo) denoted by \(\mathcal{A}^{R}\). Definition 2: Given a randomized (Monte Carlo) integration formula for the functions from the space \(\mathbf{W}^{k}\), we define the integration error  
\[err(f,A^{R})\equiv\int_{U^{d}}f(\mathbf{x})d\mathbf{x}-A^{R}(f,n)\]  
by the probability error \(\varepsilon_{P}(f)\) in the sense that \(\varepsilon_{P}(f)\) is the least possible real number, such that  
\[Pr\Big{(}\Big{|}err(f,A^{R})\Big{|}<\varepsilon_{P}(f)\Big{)}\geq P,\]  
and the mean square error  
\[r(f)=\Big{\{}E\Big{[}err^{2}(f,A^{R})\Big{]}\Big{\}}^{1/2}.\]  
We assume that it suffices to obtain an \(\varepsilon_{P}(f)\)-approximation to the solution with a probability \(0<P<1\). If we allow equality, i.e., \(0<P\leq 1\) in Definition 2, then \(\varepsilon_{P}(f)\) can be used as an accuracy measure for both randomized and deterministic algorithms.