共查询到20条相似文献,搜索用时 25 毫秒
1.
Let
be a finite field withq elements and
a rational function over
. No polynomial-time deterministic algorithm is known for the problem of deciding whetherf induces a permutation on
. The problem has been shown to be in co-R
co-NP, and in this paper we prove that it is inR
NP and hence inZPP, and it is deterministic polynomial-time reducible to the problem of factoring univariate polynomials over
. Besides the problem of recognizing prime numbers, it seems to be the only natural decision problem inZPP unknown to be inP. A deterministic test and a simple probabilistic test for permutation functions are also presented. 相似文献
2.
Any given n×n matrix A is shown to be a restriction, to the A-invariant subspace, of a nonnegative N×N matrix B of spectral radius (B) arbitrarily close to (A). A difference inclusion
, where
is a compact set of matrices, is asymptotically stable if and only if
can be extended to a set
of nonnegative matrices B with
or
. Similar results are derived for differential inclusions. 相似文献
3.
I. V. Gaishun 《Automation and Remote Control》2002,63(11):1717-1723
A class of two-parameter discrete systems defined on the ring
of class of residues of integers
modulo m is studied. All solutions are shown to be periodic, stability conditions (equality of solutions to zero, beginning from a certain instant) and a controllability condition are formulated. Controllability is shown to guarantee stabilizability. 相似文献
4.
D. Yu. Nogin 《Problems of Information Transmission》2005,41(2):91-104
We prove that the weight function wt:
on a set of messages uniquely determines a linear code of dimension k up to equivalence. We propose a natural way to extend the rth generalized Hamming weight, that is, a function on r-subspaces of a code C, to a function on
. Using this, we show that, for each linear code C and any integer r ≤ k = dim C, a linear code exists whose weight distribution corresponds to a part of the generalized weight spectrum of C, from the rth weights to the kth. In particular, the minimum distance of this code is proportional to the rth generalized weight of C.__________Translated from Problemy Peredachi Informatsii, No. 2, 2005, pp. 26–41.Original Russian Text Copyright © 2005 by Nogin.Supported in part by the Russian Foundation for Basic Research, project no. 02-01-01041, and INTAS, grant no. 00-738. 相似文献
5.
Given a nonempty set of functions
where a = x
0 < ... < x
n
= b are known nodes and w
i
, i = 0,...,n, d
i
, i = 1,..., n, known compact intervals, the main aim of the present paper is to show that the functions
and
exist, are in F, and are easily computable. This is achieved essentially by giving simple formulas for computing two vectors
with the properties
] is the interval hull of (the tolerance polyhedron) T;
iff T 0 iff F 0.
, can serve for solving the following problem: Assume that is a monotonically increasing functional on the set of Lipschitz-continuous functions f : [a,b] R (e.g. (f) =
a
b
f(x) dx or (f) = min f([a,b]) or (f) = max f([a,b])), and that the available information about a function g : [a,b] R is "g F," then the problem is to find the best possible interval inclusion of (g). Obviously, this inclusion is given by the interval [(
,(
)]. Complete formulas for computing this interval are given for the case (f) =
a
b
f(x) dx. 相似文献
6.
M. A. Shepilov 《Cybernetics and Systems Analysis》1987,23(2):233-238
Conclusion The obvious deficiency of the method (1.3), (1.9) is the possible difficulty of the operation
. In connection with this one can note that all the above given statements remain valid if the number
is replaced by some positive lower bound of |f(t
k
,x)| on
.In computational methods, the presence of the Lipschitz constant is considered as a deficiency. In connection with this we can note that the Lipschitz constant L can be replaced by any of its upper estimates. For example, for a differentiable function f(z) one can take
.Translated from Kibernetika, No. 2, pp. 71–74, March–April, 1987. 相似文献
7.
Mohammad A. Shokrollahi 《Computational Complexity》1991,1(2):157-181
In the present paper we shall show that the rank of the finite field
regarded as an
-algebra has one of the two values 2n or 2n+1 ifn satisfies 1/2q+1<n<1/2(m(q)–2). Herem(q) denotes the maximum number of
-rational points of an algebraic curve of genus 2 over
. Using results of Davenport-Hasse, Honda and Rück we shall give lower bounds form(q) which are close to the Hasse-Weil bound
. For specialq we shall further show thatm(q) is equal to the Hasse-Weil bound. 相似文献
8.
9.
A class of linear positive, trace preserving maps in M
n is given in terms of affine maps in
which map the closed unit ball into itself. 相似文献
10.
The paper describes an improved algorithm for computing cohomologies of Lie (super)algebras. The original algorithm developed earlier by the author of this paper is based on the decomposition of the entire cochain complex into minimal subcomplexes. The suggested improvement consists in the replacement of the arithmetic of rational or integer numbers by a more efficient arithmetic of modular fields and the use of the relationship dim H
k(
p) dimH
k() between the dimensions of cohomologies over an arbitrary modular field
p = /p and the filed of rational numbers . This inequality allows us to rapidly find subcomplexes for which dimH
k(
p) > 0 (the number of such subcomplexes is usually not great) using computations over an arbitrary
p and, then, carry out all required computations over in these subcomplexes. 相似文献
11.
In this paper, we discuss the minimal number of observables Q
1, ..., Q
, where expectation values at some time instants t
1, ..., t
r determine the trajectory of a d-level quantum system (qudit) governed by the Gaussian semigroup
. We assume that the macroscopic information about the system in question is given by the mean values E
j(Q
i) = tr(Q
i(t
j)) of n selfadjoint operators Q
1, ..., Q
n at some time instants t
1 < t
2 < ... < t
r, where n < d
2– 1 and r deg (,
). Here (,
) stands for the minimal polynomial of the generator
of the Gaussian flow (t). 相似文献
12.
A linear difference operator L with polynomial coefficients and a function F(x) satisfying the equation LF(x) = 0 are considered. The function is assumed to be analytic in the interval (–,
d), where > 0. In the paper, an implementation of an algorithm suggested by S.A. Abramov and M. van Hoeij for finding conditions that guarantee analyticity of F(x) on the entire real axis
is presented. The analyticity conditions are linear relations for values of F(x) and its derivatives at a given point belonging to the half-interval [0, d). A procedure for computing values of F(x) and its derivatives up to a prescribed order at a given point x
0
is also implemented. Examples illustrating the program operation are presented. 相似文献
13.
As is well known, a finite field
n
= GF(q
n
) can be described in terms of n × n matrices A over the field
= GF(q) such that their powers A
i
, i = 1, 2, ..., q
n
– 1, correspond to all nonzero elements of the field. It is proved that, for fields
n
of characteristic 2, such a matrix A can be chosen to be symmetric. Several constructions of field-representing symmetric matrices are given. These matrices A
i
together with the all-zero matrix can be considered as a
n
-linear matrix code in the rank metric with maximum rank distance d = n and maximum possible cardinality q
n
. These codes are called symmetric rank codes. In the vector representation, such codes are maximum rank distance (MRD) linear [n, 1, n] codes, which allows one to use known rank-error-correcting algorithms. For symmetric codes, an algorithm of erasure symmetrization is proposed, which considerably reduces the decoding complexity as compared with standard algorithms. It is also shown that a linear [n, k, d = n – k + 1] MRD code
k
containing the above-mentioned one-dimensional symmetric code as a subcode has the following property: the corresponding transposed code is also
n
-linear. Such codes have an extended capability of correcting symmetric errors and erasures. 相似文献
14.
Let a linear homogeneous ordinary differential equation with polynomial coefficients over a field
be given. For a singular point of the equation, the fundamental system of formal solutions that contain a finite number of power series with coefficients belonging to the algebraic extension of
can be constructed by known algorithms. In this paper, an algorithm is suggested for construction of a space of formal solutions such that all series containing in these solutions have m-hypergeometric coefficients. The implementation of the algorithm in the computer algebra system Maple is discussed. 相似文献
15.
Let
be some set of orientations, that is,
. We consider the consequences of defining visibility based on curves that are monotone with respect to the orientations in
. We call such curves
-staircases. Two points p andq in a polygonP are said to
-see each other if an
-staircase fromp toq exists that is completely contained inP. The
-kernel of a polygonP is then the set of all points which
-see all other points. The
-kernel of a simple polygon can be obtained as the intersection of all {}-kernels, with
. With the help of this observation we are able to develop an
algorithm to compute the
-kernel of a simple polygon, for finite
. We also show how to compute theexternal
-kernel of a polygon in optimal time
. The two algorithms are combined to compute the (
-kernel of a polygon with holes in time
.This work was supported by the Deutsche Forschungsgemeinschaft under Grant No. Ot 64/5-4 and the Natural Sciences and Engineering Research Council of Canada and Information Technology Research Centre of Ontario. 相似文献
16.
A new algorithm for solving systems of linear equations Ax = b in an Euclidean domain is suggested. In the case of the ring
of integers, the complexity of this algorithm is O
(n
3
mlog2
||A||), where
n)$$
" align="middle" border="0">
is a matrix of rank n and
, if standard algorithms for the multiplication of integers and matrices are used. Under the same conditions, the best algorithm of this kind among those published earlier, which was suggested by Labahn and Storjohann in [1], has complexity O
(n
4
mlog2
||A||). True, when using fast algorithms for the multiplication of numbers and matrices, the theoretical complexity estimate for the latter algorithm is O
(n
mlog2
||A||), which is better than the similar estimate O
(n
3
mlog||A||) for the new algorithm. 相似文献
17.
Composing the Carlet map with the inverse Gray map, a new family of cyclic quaternary codes is constructed from 5-cyclic
-codes. This new family of codes is inspired by the quaternary Shanbag–Kumar–Helleseth family, a recent improvement on the Delsarte–Goethals family. We conjecture that these
-codes are not linear. As applications, we construct families of low-correlation quadriphase and biphase sequences. 相似文献
18.
19.
Remco Duits Michael Felsberg Gösta Granlund Bart ter Haar Romeny 《International Journal of Computer Vision》2007,72(1):79-102
Inspired by the early visual system of many mammalians we consider the construction of-and reconstruction from- an orientation
score
as a local orientation representation of an image,
. The mapping
is a wavelet transform
corresponding to a reducible representation of the Euclidean motion group onto
and oriented wavelet
. This wavelet transform is a special case of a recently developed generalization of the standard wavelet theory and has the
practical advantage over the usual wavelet approaches in image analysis (constructed by irreducible representations of the
similitude group) that it allows a stable reconstruction from one (single scale) orientation score. Since our wavelet transform
is a unitary mapping with stable inverse, we directly relate operations on orientation scores to operations on images in a
robust manner.
Furthermore, by geometrical examination of the Euclidean motion group
, which is the domain of our orientation scores, we deduce that an operator Φ on orientation scores must be left invariant
to ensure that the corresponding operator
on images is Euclidean invariant. As an example we consider all linear second order left invariant evolutions on orientation
scores corresponding to stochastic processes on G. As an application we detect elongated structures in (medical) images and automatically close the gaps between them.
Finally, we consider robust orientation estimates by means of channel representations, where we combine robust orientation
estimation and learning of wavelets resulting in an auto-associative processing of orientation features. Here linear averaging
of the channel representation is equivalent to robust orientation estimation and an adaptation of the wavelet to the statistics
of the considered image class leads to an auto-associative behavior of the system.
The Netherlands Organization for Scientific Research is gratefully acknowledged for financial support. This work has been
supported by EC Grant IST-2003-004176 COSPAL. 相似文献
20.
We study mutually unbiased maximally entangled bases (MUMEB’s) in bipartite system \(\mathbb {C}^d\otimes \mathbb {C}^d (d \ge 3)\). We generalize the method to construct MUMEB’s given in Tao et al. (Quantum Inf Process 14:2291–2300, 2015), by using any commutative ring R with d elements and generic character of \((R,+)\) instead of \(\mathbb {Z}_d=\mathbb {Z}/d\mathbb {Z}\). Particularly, if \(d=p_1^{a_1}p_2^{a_2}\ldots p_s^{a_s}\) where \(p_1, \ldots , p_s\) are distinct primes and \(3\le p_1^{a_1}\le \cdots \le p_s^{a_s}\), we present \(p_1^{a_1}-1\) MUMEB’s in \(\mathbb {C}^d\otimes \mathbb {C}^d\) by taking \(R=\mathbb {F}_{p_1^{a_1}}\oplus \cdots \oplus \mathbb {F}_{p_s^{a_s}}\), direct sum of finite fields (Theorem 3.3). 相似文献