共查询到20条相似文献,搜索用时 31 毫秒
1.
Given a “black box” function to evaluate an unknown rational polynomial
f ? \mathbbQ[x]f \in {\mathbb{Q}}[x] at points modulo a prime p, we exhibit algorithms to compute the representation of the polynomial in the sparsest shifted power basis. That is, we determine
the sparsity $t \in {\mathbb{Z}}_{>0}$t \in {\mathbb{Z}}_{>0}, the shift
a ? \mathbbQ\alpha \in {\mathbb{Q}}, the exponents 0 £ e1 < e2 < ? < et{0 \leq e_{1} < e_{2} < \cdots < e_{t}}, and the coefficients
c1, ?, ct ? \mathbbQ \{0}c_{1}, \ldots , c_{t} \in {\mathbb{Q}} \setminus \{0\} such that
f(x) = c1(x-a)e1+c2(x-a)e2+ ?+ct(x-a)etf(x) = c_{1}(x-\alpha)^{e_{1}}+c_{2}(x-\alpha)^{e_{2}}+ \cdots +c_{t}(x-\alpha)^{e_{t}} 相似文献
2.
We prove that the concept class of disjunctions cannot be pointwise approximated by linear combinations of any small set of
arbitrary real-valued functions. That is, suppose that there exist functions f1, ?, fr\phi_{1}, \ldots , \phi_{r} : {− 1, 1}n →
\mathbbR{\mathbb{R}} with the property that every disjunction f on n variables has $\|f - \sum\nolimits_{i=1}^{r} \alpha_{i}\phi
_{i}\|_{\infty}\leq 1/3$\|f - \sum\nolimits_{i=1}^{r} \alpha_{i}\phi
_{i}\|_{\infty}\leq 1/3 for some reals a1, ?, ar\alpha_{1}, \ldots , \alpha_{r}. We prove that then $r \geq
exp \{\Omega(\sqrt{n})\}$r \geq
exp \{\Omega(\sqrt{n})\}, which is tight. We prove an incomparable lower bound for the concept class of decision lists. For the concept class of majority
functions, we obtain a lower bound of W(2n/n)\Omega(2^{n}/n) , which almost meets the trivial upper bound of 2n for any concept class. These lower bounds substantially strengthen and generalize the polynomial approximation lower bounds of Paturi
(1992) and show that the regression-based agnostic learning algorithm of Kalai et al. (2005) is optimal. 相似文献
3.
The “Priority Algorithm” is a model of computation introduced by Borodin, Nielsen and Rackoff ((Incremental) Priority algorithms,
Algorithmica 37(4):295–326, 2003) which formulates a wide class of greedy algorithms. For an arbitrary set
\mathbbS\mathbb{S}
of jobs, we are interested in whether or not there exists a priority algorithm that gains optimal profit on every subset of
\mathbbS\mathbb{S}
. In the case where the jobs are all intervals, we characterize such sets
\mathbbS\mathbb{S}
and give an efficient algorithm (when
\mathbbS\mathbb{S}
is finite) for determining this. We show that in general, however, the problem is NP-hard. 相似文献
4.
Rahul Tripathi 《Theory of Computing Systems》2010,46(2):193-221
The 1-versus-2 queries problem, which has been extensively studied in computational complexity theory, asks in its generality whether every efficient
algorithm that makes at most 2 queries to a Σ
k
p
-complete language L
k
has an efficient simulation that makes at most 1 query to L
k
. We obtain solutions to this problem for hypotheses weaker than previously considered. We prove that:
5.
In this paper, we derive unitary Yang-Baxter
\breveR(q, j){\breve{R}(\theta, \varphi)} matrices from the
8×8 \mathbbM{8\times8\,\mathbb{M}} matrix and the 4 × 4 M matrix by Yang-Baxteration approach, where
\mathbbM/M{\mathbb{M}/M} is the image of the braid group representation. In Yang-Baxter systems, we explore the evolution of tripartite negativity
for three qubits Greenberger-Horne-Zeilinger (GHZ)-type states and W-type states and investigate the evolution of the bipartite
concurrence for 2 qubits Bell-type states. We show that tripartite entanglement sudden death (ESD) and bipartite ESD all can
happen in Yang-Baxter systems and find that ESD all are sensitive to the initial condition. Interestingly, we find that in
the Yang-Baxter system, GHZ-type states can have bipartite entanglement and bipartite ESD, and find that in some initial conditions,
W-type states have tripartite ESD while they have no bipartite Entanglement. It is worth noting that the meaningful parameter
j{\varphi} has great influence on bipartite ESD for two qubits Bell-type states in the Yang-Baxter system. 相似文献
6.
In classical constraint satisfaction, redundant modeling has been shown effective in increasing constraint propagation and
reducing search space for many problem instances. In this paper, we investigate, for the first time, how to benefit the same
from redundant modeling in weighted constraint satisfaction problems (WCSPs), a common soft constraint framework for modeling optimization and over-constrained problems. Our work focuses on
a popular and special class of problems, namely, permutation problems. First, we show how to automatically generate a redundant permutation WCSP model from an existing permutation WCSP using
generalized model induction. We then uncover why naively combining mutually redundant permutation WCSPs by posting channeling constraints as hard constraints
and relying on the standard node consistency (NC*) and arc consistency (AC*) algorithms would miss pruning opportunities, which are available even in a single model. Based on these observations,
we suggest two approaches to handle the combined WCSP models. In our first approach, we propose
m\text -NC\text c*m\text {-NC}_{\text c}^* and
m\text -AC\text c*m\text {-AC}_{\text c}^* and their associated algorithms for effectively enforcing node and arc consistencies in a combined model with m sub-models. The two notions are strictly stronger than NC* and AC* respectively. While the first approach specifically refines
NC* and AC* so as to apply to combined models, in our second approach, we propose a parameterized local consistency LB(m,Φ). The consistency can be instantiated with any local consistency Φ for single models and applied to a combined model with m sub-models. We also provide a simple algorithm to enforce LB(m,Φ). With the two suggested approaches, we demonstrate their applicabilities on several permutation problems in the experiments.
Prototype implementations of our proposed algorithms confirm that applying
2\text -NC\text c*, 2\text -AC\text c*2\text {-NC}_{\text c}^*,\;2\text {-AC}_{\text c}^*, and LB(2,Φ) on combined models allow far more constraint propagation than applying the state-of-the-art AC*, FDAC*, and
EDAC* algorithms on single models of hard benchmark problems. 相似文献
7.
VPSPACE and a Transfer Theorem over the Reals 总被引:1,自引:1,他引:0
We introduce a new class VPSPACE of families of polynomials. Roughly speaking, a family of polynomials is in VPSPACE if its
coefficients can be computed in polynomial space. Our main theorem is that if (uniform, constant-free) VPSPACE families can
be evaluated efficiently then the class
\sf PAR\mathbb R\sf {PAR}_{\mathbb {R}} of decision problems that can be solved in parallel polynomial time over the real numbers collapses to
\sfP\mathbb R\sf{P}_{\mathbb {R}}. As a result, one must first be able to show that there are VPSPACE families which are hard to evaluate in order to separate
\sfP\mathbb R\sf{P}_{\mathbb {R}} from
\sfNP\mathbb R\sf{NP}_{\mathbb {R}}, or even from
\sfPAR\mathbb R\sf{PAR}_{\mathbb {R}}. 相似文献
8.
Davod Khojasteh Salkuyeh 《Soft Computing - A Fusion of Foundations, Methodologies and Applications》2011,15(5):953-961
In this paper, we consider the fuzzy Sylvester matrix equation AX+XB=C,AX+XB=C, where
A ? \mathbbRn ×nA\in {\mathbb{R}}^{n \times n} and
B ? \mathbbRm ×mB\in {\mathbb{R}}^{m \times m} are crisp M-matrices, C is an n×mn\times m fuzzy matrix and X is unknown. We first transform this system to an (mn)×(mn)(mn)\times (mn) fuzzy system of linear equations. Then, we investigate the existence and uniqueness of a fuzzy solution to this system. We
use the accelerated over-relaxation method to compute an approximate solution to this system. Some numerical experiments are
given to illustrate the theoretical results. 相似文献
9.
In Valiant’s theory of arithmetic complexity, the classes VP and VNP are analogs of P and NP. A fundamental problem concerning
these classes is the Permanent and Determinant Problem: Given a field
\mathbbF{\mathbb{F}} of characteristic ≠ 2, and an integer n, what is the minimum m such that the permanent of an n × n matrix X = (xij) can be expressed as a determinant of an m × m matrix, where the entries of the determinant matrix are affine linear functions of xij ’s, and the equality is in
\mathbbF[X]{\mathbb{F}}[{\bf X}]. Mignon and Ressayre (2004) proved a quadratic lower bound m = W(n2)m = \Omega(n^{2}) for fields of characteristic 0. We extend the Mignon–Ressayre quadratic lower bound to all fields of characteristic ≠ 2. 相似文献
10.
Using ideas from automata theory, we design the first polynomial deterministic identity testing algorithm for the sparse noncommutative polynomial identity testing problem. Given a noncommuting black-box polynomial
f ? \mathbb F{x1,?,xn}f \in {\mathbb F}\{x_{1},\ldots,x_n\} of degree d with at most t monomials, where the variables xi are noncommuting, we give a deterministic polynomial identity test that checks if C o 0C \equiv 0 and runs in time polynomial in d, n, |C|, and t. Our algorithm evaluates the black-box polynomial for xi assigned to matrices over
\mathbbF{\mathbb{F}} and, in fact, reconstructs the entire polynomial f in time polynomial in n, d and t. 相似文献
11.
Ji?í Mo?ko? 《Soft Computing - A Fusion of Foundations, Methodologies and Applications》2012,16(1):101-107
Let
\Upomega\Upomega be a complete residuated lattice. Let
SetR(\Upomega){\mathbf{SetR}}(\Upomega) be the category of sets with similarity relations with values in
\Upomega\Upomega (called
\Upomega\Upomega-sets), which is an analogy of the category of classical sets with relations as morphisms. A fuzzy set in an
\Upomega\Upomega-set in the category
SetR(\Upomega){\mathbf{SetR}}(\Upomega) is a morphism from
\Upomega\Upomega-set to a special
\Upomega\Upomega-set
(\Upomega,?),(\Upomega,\leftrightarrow), where ?\leftrightarrow is the biresiduation operation in
\Upomega.\Upomega. In the paper, we prove that fuzzy sets in
\Upomega\Upomega-sets in the category
SetR(\Upomega){\mathbf{SetR}}(\Upomega) can be expressed equivalently as special cut systems
(Ca)a ? \Upomega.(C_{\alpha})_{\alpha\in\Upomega}. 相似文献
12.
A set A is nontrivial for the linear-exponential-time class E=DTIME(2
lin
) if for any k≥1 there is a set B
k
∈E such that B
k
is (p-m-)reducible to A and Bk ? DTIME(2k·n)B_{k} \not\in \mathrm{DTIME}(2^{k\cdot n}). I.e., intuitively, A is nontrivial for E if there are arbitrarily complex sets in E which can be reduced to A. Similarly, a set A is nontrivial for the polynomial-exponential-time class EXP=DTIME(2
poly
) if for any k≥1 there is a set [^(B)]k ? EXP\hat{B}_{k} \in \mathrm {EXP} such that [^(B)]k\hat{B}_{k} is reducible to A and [^(B)]k ? DTIME(2nk)\hat{B}_{k} \not\in \mathrm{DTIME}(2^{n^{k}}). We show that these notions are independent, namely, there are sets A
1 and A
2 in E such that A
1 is nontrivial for E but trivial for EXP and A
2 is nontrivial for EXP but trivial for E. In fact, the latter can be strengthened to show that there is a set A∈E which is weakly EXP-hard in the sense of Lutz (SIAM J. Comput. 24:1170–1189, 11) but E-trivial. 相似文献
13.
Sayed Yousef Monir Vaghefi Sayed Mahmoud Monir Vaghefi 《Neural computing & applications》2011,20(7):1055-1060
A multilayer feedforward neural network with two hidden layers was designed and developed for prediction of the phosphorus
content of electroless Ni–P coatings. The input parameters of the network were the pH, metal turnover, and loading of an electroless
bath. The output parameter was the phosphorus content of the electroless Ni–P coatings. The temperature and molar rate of
the bath were constant (
91° \textC, 0.4 \textNi\text + + /\textH2 \textPO2 - - 91^\circ {\text{C}},\:0.4\,{\text{Ni}}^{{{\text{ + + }}}} /{\text{H}}_{2} {\text{PO}}_{2}^{{ - - }} ). The network was trained and tested using the data gathered from our own experiments. The goal of the study was to estimate
the accuracy of this type of neural network in prediction of the phosphorus content. The study result shows that this type
of network has high accuracy even when the number of hidden neurons is very low. Some comparison between the network’s predictions
and own experimental data are given. 相似文献
14.
We study algorithms simulating a system evolving with Hamiltonian H = ?j=1m Hj{H = \sum_{j=1}^m H_j} , where each of the H
j
, j = 1, . . . ,m, can be simulated efficiently. We are interested in the cost for approximating
e-iHt, t ? \mathbbR{e^{-iHt}, t \in \mathbb{R}} , with error e{\varepsilon} . We consider algorithms based on high order splitting formulas that play an important role in quantum Hamiltonian simulation.
These formulas approximate e
−iHt
by a product of exponentials involving the H
j
, j = 1, . . . ,m. We obtain an upper bound for the number of required exponentials. Moreover, we derive the order of the optimal splitting method that minimizes our upper bound. We show significant speedups relative to previously known results. 相似文献
15.
Katarína Čunderlíková 《Soft Computing - A Fusion of Foundations, Methodologies and Applications》2010,14(3):229-234
The ergodic theory and particularly the individual ergodic theorem were studied in many structures. Recently the individual
ergodic theorem has been proved for MV-algebras of fuzzy sets (Riečan in Czech Math J 50(125):673–680, 2000; Riečan and Neubrunn in Integral, measure, and ordering. Kluwer, Dordrecht, 1997) and even in general MV-algebras (Jurečková in Int J Theor Phys 39:757–764, 2000). The notion of almost everywhere equality of observables was introduced by Riečan and Jurečková (Int J Theor Phys 44:1587–1597,
2005). They proved that the limit of Cesaro means is an invariant observable for P-observables. In Lendelová (Int J Theor Phys 45(5):915–923, 2006c) showed that the assumption of P-observable can be omitted. In this paper we prove the individual ergodic theorem on family of IF-events and show that each
P {\mathcal{P}} -preserving transformation in this family can be expressed by two corresponding
P\flat,P\sharp {\mathcal{P}}^\flat,{\mathcal{P}}^\sharp -preserving transformations in tribe T. {\mathcal{T}}. 相似文献
16.
Yan Mo Xue-ping Wang 《Soft Computing - A Fusion of Foundations, Methodologies and Applications》2011,15(9):1835-1843
An n×nn{\times}n fuzzy matrix A is called realizable if there exists an n×tn{\times}t fuzzy matrix B such that
A=B\odot BT,A=B\odot B^{T}, where
\odot\odot is the max–min composition. Let
r(A)=min{p:A=B\odot BT, B ? Ln×p}.r(A)={min}\{p:A=B\odot B^{T}, B\in L^{n\times p}\}. Then r(A)r(A) is called the content of A. Since 1982, how to calculate r(A) for a given n×nn{\times}n realizable fuzzy matrix A was a focus problem, many researchers have made a lot of research work. X. P. Wang in 1999 gave an algorithm to find the
fuzzy matrix B and calculate r(A) within [r(A)]n2[r(A)]^{n^{2}} steps. Therefore, to find a simpler algorithm is a problem what we have to consider. This paper makes use of the symmetry
of the realizable fuzzy matrix A to simplify the algorithm of content r(A)r(A) based on the work of Wang (Chin Ann Math A 6: 701–706, 1999). 相似文献
17.
Truong Nguyen-Ba Huong Nguyen-Thu Thierry Giordano Rémi Vaillancourt 《Journal of scientific computing》2012,50(1):63-90
Optimal, 7-stage, explicit, strong-stability-preserving (SSP) Hermite–Birkhoff (HB) methods of orders 4 to 8 with nonnegative
coefficients are constructed by combining linear k-step methods with a 7-stage Runge–Kutta (RK) method of order 4. Compared to Huang’s hybrid methods of the same order, the
new methods generally have larger effective SSP coefficients and larger maximum effective CFL numbers,
\textnum\texteff\text{num}_{\text{eff}}, on Burgers’ equation, independently of the number k of steps, especially when k is small for both methods. Based on
\textnum\texteff\text{num}_{\text{eff}}, some new methods of order 4 compare favorably with other methods of the same order, including RK104 of Ketcheson. The new
SSP HB methods are listed in their Shu–Osher representation in Appendix. 相似文献
18.
We consider the following type of online variance minimization problem: In every trial t our algorithms get a covariance matrix C
t
and try to select a parameter vector w
t−1 such that the total variance over a sequence of trials ?t=1T (wt-1)T Ctwt-1\sum_{t=1}^{T} (\boldsymbol {w}^{t-1})^{\top} \boldsymbol {C}^{t}\boldsymbol {w}^{t-1} is not much larger than the total variance of the best parameter vector u chosen in hindsight. Two parameter spaces in ℝ
n
are considered—the probability simplex and the unit sphere. The first space is associated with the problem of minimizing
risk in stock portfolios and the second space leads to an online calculation of the eigenvector with minimum eigenvalue of
the total covariance matrix ?t=1T Ct\sum_{t=1}^{T} \boldsymbol {C}^{t}. For the first parameter space we apply the Exponentiated Gradient algorithm which is motivated with a relative entropy regularization.
In the second case, the algorithm has to maintain uncertainty information over all unit directions u. For this purpose, directions are represented as dyads uu
⊤ and the uncertainty over all directions as a mixture of dyads which is a density matrix. The motivating divergence for density
matrices is the quantum version of the relative entropy and the resulting algorithm is a special case of the Matrix Exponentiated
Gradient algorithm. In each of the two cases we prove bounds on the additional total variance incurred by the online algorithm
over the best offline parameter. 相似文献
19.
The concept of $(\overline{\in},\overline{\in} \vee \overline{q})
20.
CAO FeiLong ZHANG YongQuan & XU ZongBen College of Science China Jiliang University Hangzhou China Institute of Information System Sciences Xi’an Jiaotong University Xi’an 《中国科学F辑(英文版)》2009,52(8):1321-1327
Let SFd and Πψ,n,d = { nj=1bjψ(ωj·x+θj) :bj,θj∈R,ωj∈Rd} be the set of periodic and Lebesgue’s square-integrable functions and the set of feedforward neural network (FNN) functions, respectively. Denote by dist (SF d, Πψ,n,d) the deviation of the set SF d from the set Πψ,n,d. A main purpose of this paper is to estimate the deviation. In particular, based on the Fourier transforms and the theory of approximation, a lower estimation for dist (SFd, Πψ,n,d) is proved. That is, dist(SF d, Πψ,n,d) (nlogC2n)1/2 . T... 相似文献
|