共查询到20条相似文献,搜索用时 31 毫秒
1.
DANIEL RICHARDSON 《Journal of Symbolic Computation》1997,24(6):627-645
An elementary point is a point in complexnspace, which is an isolated, nonsingular solution ofnequations innvariables, each equation being either of the formp = 0, wherepis a polynomial in
[x1,…,xn], or of the formxj − exi = 0. An elementary number is the polynomial image of an elementary point. In this article a semi algorithm is given to decide whether or not a given elementary number is zero. It is proved that this semi algorithm is an algorithm, i.e. that it always terminates, unless it is given a problem containing a counterexample to Schanuel’s conjecture. 相似文献
2.
We present a function field sieve method for discrete logarithms over finite fields. This method is an analog of the number field sieve method originally developed for factoring integers. It is asymptotically faster than the previously known algorithms when applied to finite fields Fpn, where p6n. 相似文献
3.
Peter Dolan 《Annals of Mathematics and Artificial Intelligence》1992,6(1-3):17-25
In this paper we will consider random graphsG
n,p
,p=n
–
a rational number between 0 and 1. We show that there is no decision procedure that separates those first order statements that hold almost always inG
n,p
from those whose negation holds almost always. 相似文献
4.
In this paper we study parallel batch scheduling problems with bounded batch capacity and equal-length jobs in a single and
parallel machine environment. It is shown that the feasibility problem 1|p-batch,b<n,r
j
,p
j
=p,C
j
≤d
j
|− can be solved in O(n
2) time and that the problem of minimizing the maximum lateness can be solved in O(n
2log n) time. For the parallel machine problem P|p-batch,b<n,r
j
,p
j
=p,C
j
≤d
j
|− an O(n
3log n)-time algorithm is provided, which can also be used to solve the problem of minimizing the maximum lateness in O(n
3log 2
n) time. 相似文献
5.
Given n points, called terminals, in the plane ℝ2 and a positive integer k, the bottleneck Steiner tree problem is to find k Steiner points from ℝ2 and a spanning tree on the n+k points that minimizes its longest edge length. Edge length is measured by an underlying distance function on ℝ2, usually, the Euclidean or the L
1 metric. This problem is known to be NP-hard. In this paper, we study this problem in the L
p
metric for any 1≤p≤∞, and aim to find an exact algorithm which is efficient for small fixed k. We present the first fixed-parameter tractable algorithm running in f(k)⋅nlog 2
n time for the L
1 and the L
∞ metrics, and the first exact algorithm for the L
p
metric for any fixed rational p with 1<p<∞ whose time complexity is f(k)⋅(n
k
+nlog n), where f(k) is a function dependent only on k. Note that prior to this paper there was no known exact algorithm even for the L
2 metric. 相似文献
6.
Mohammad A. Shokrollahi 《Computational Complexity》1992,2(1):67-96
LetN
max(q) denote the maximum number of points of an elliptic curve over F
q
. Given a prime powerq=p
f
and an integern satisfying 1/2q+1<n(N
max(q)–2)/2, we present an algorithm which on inputq andn produces an optimal bilinear algorithm of length 2n for multiplication in F
q
n
/F
q
. The algorithm takes roughlyO(q
4+n
4logq) F
q
-operations or equivalentlyO((q
4+n
4logq)f
2log2
p) bit-operations to compute the output data. 相似文献
7.
Let G=(V,E) be a complete undirected graph, with node set V={v
1
, . . ., v
n
} and edge set E . The edges (v
i
,v
j
) ∈ E have nonnegative weights that satisfy the triangle inequality. Given a set of integers K = { k
i
}
i=1
p
, the minimum K-cut problem is to compute disjoint subsets with sizes { k
i
}
i=1
p
, minimizing the total weight of edges whose two ends are in different subsets. We demonstrate that for any fixed p it is possible to obtain in polynomial time an approximation of at most three times the optimal value. We also prove bounds
on the ratio between the weights of maximum and minimum cuts.
Received September 4, 1997; revised July 15, 1998. 相似文献
8.
In our previous work [1] occlusion phenomena were considered as a foundation for development of geometrical structures in the visual field. The laws of occlusion were adapted to form the basis of an axiomatic system. Occlusion is formalized as a ternary relation and its properties include symmetry and transistivity. This leads to the definition of an abstract visual space (AVS). The geometry of an AVS is the subject of this research. Typical examples of an AVS are the convex open subsets of an n-dimensional real affine space for n2 or more generally, the convex open subsets of any n-dimensional affine space over some totally ordered field F, commutative or noncommutative. In an AVS we define such geometrical objects as lines, planes, convex bodies, closed and open subsets, etc. For any n-dimensional (n3) AVS X we construct an n-dimensional projective space P
F
n over a totally ordered commutative or noncommutative field F and produce an embedding i: X xP
F
n such that the image i(X) is open in P
F
n and every line l in X is of the form l=i
-1 (Li(X)) for some line L in P
F
n. The mapping i and the field F depend on X and are unique up to isomorphism. We obtain a characterization of X via this embedding which is complete in the case of archimedean fields F. If F=R, the field of real numbers, i induces an embedding j: X ¶ A
R
n and j(X) is a convex open subset of an affine space A
R
n. If FR there can exist other types of AVS. 相似文献
9.
We study the asymptotic behaviour of the eigenvalues of Hermitiann×n block Topelitz matricesT
n
, withk×k blocks, asn tends to infinity. No hypothesis is made concerning the structure of the blocks. Such matrices{T
n
} are generated by the Fourier coefficients of a Hermitian matrix valued functionf∈L
2, and we study the distribution of their eigenvalues for largen, relating their behaviour to some properties of the functionf. We also study the eigenvalues of the preconditioned matrices{P
n
−1
Tn}, where the sequence{P
n
} is generated by a positive definite matrix valued functionp. We show that the spectrum of anyP
n
−1
T
n
is contained in the interval [r, R], wherer is the smallest andR the largest eigenvalue ofp
−1
f. We also prove that the firstm eigenvalues ofP
n
−1
Tn tend tor and the lastm tend toR, for anym fixed. Finally, exact limit values for both the condition number and the conjugate gradient convergence factor for the preconditioned
matricesP
n
−1
Tn are computed. 相似文献
10.
In this paper, we are concerned with the delay difference equations of the form(*) (*)where pn ≥ 0 and k is a positive integer. We prove by using a new technique thatguarantees that all solutions of equation (*) oscillate, which improves many previous well-known results. In particular, our theorems also fit the case where Σn−1i=n−kpi ≤ kk+1/(k + 1)k+1. In addition, we present a nonoscillation sufficient condition for equation (*). 相似文献
yn+1 − yn + pnyn−k = 0, N = 0, 1, 2, …,
11.
Helmut Alt 《Acta Informatica》1979,12(1):33-61
Summary Using methods from linear algebra and crossing-sequence arguments it is shown that logarithmic space is necessary for the
recognition of all context-free nonregular subsets of {a1}* ... {an}*, where {a1,...,an} is some alphabet. It then follows that log n is a lower bound on the space complexity for the recognition of any bounded or deterministic non-regular context-free language. 相似文献
12.
In this note, we outline a very simple algorithm for the following problem: Given a set S of n points p1,p2,p3,…,pn in the plane, we have O(n2) segments implicitly defined on pairs of these n points. For each point pi, find a segment from this set of implicitly defined segments that is farthest from pi. The time complexity of our algorithm is in O(nh+nlogn), where n is the number of input points, and h is the number of vertices on the convex hull of S. 相似文献
13.
We consider a radio network consisting of n stations represented as the complete graph on a set of n points in the Euclidean plane with edge weights ω(p,q)=|pq|
δ
+C
p
, for some constant δ>1 and nonnegative offset costs C
p
. Our goal is to find paths of minimal energy cost between any pair of points that do not use more than some given number
k of hops. 相似文献
14.
Gang Xiang 《Reliable Computing》2006,12(1):59-64
When we have n results x1,...,xn of repeated measurement of the same quantity, the traditional statistical approach usually starts with computing their sample
average E and their sample variance V. Often, due to the inevitable measurement uncertainty, we do not know the exact values of the quantities, we only know the
intervals xi of possible values of x1 In such situations, for different possible values xi∈ xi, we get different values of the variance. We must therefore find the range V of possible values of V. It is known that in general, this problem is NP-hard. For the case when the measurements are sufficiently accurate (in some
precise sense), it is known that we can compute the interval V in quadratic time O(n2). In this paper, we describe a new algorithm for computing V that requires time O(n log(n)) (which is much faster than O(n2)). 相似文献
15.
This paper introduces a general decomposition scheme for single stage scheduling problems with jobs that have arbitrary release
dates. We assume that the objective function is monotone in the completion time of each job. The decomposition scheme has
significant theoretical and practical relevance. When assuming equal processing times, we can reduce the number of steps required
to solve several well-known nonpreemptive single machine scheduling problems by O(n3)\mathcal{O}(n^{3}), provided the processing time p is constant. Specifically, we develop new approaches that solve the problems 1|r
i
,p
i
=p|∑f
i
(C
i
) and 1|r
i
,p
i
=p|∑w
i
U
i
in O(n4)\mathcal{O}(n^{4}) time; the algorithms that have been described in the literature for these problems operate in O(n7)\mathcal{O}(n^{7}). Moreover, solution approaches for NP\mathcal{NP}-hard problems with unequal processing times may also benefit from our decomposition rule. This is particularly true if p
max/p
min is close to 1. Using the decomposition rule, either the problem size is reduced or additional information about the maximal
schedule length is obtained. 相似文献
16.
The paper proposes several mathematical models of the multidirectional associative memory (MAM) neural network by analyzing
its structure. A model of MAM with distributed delays is studied. Under some new assumptions on activation functions, 2n0[m/2]{2^{n_0[m/2]}} invariant subsets of MAM are constructed. Then the existence and the exponential stability of 2n0[m/2]{2^{n_0[m/2]}} periodic solutions located on invariant subsets are obtained by constructing a suitable Liapunov function and a Poincaré
mapping. An estimating method of the exponential convergence rate is given. The obtained results are new to MAM neural networks.
An example is given to illustrate the effectiveness of the results. 相似文献
17.
《国际计算机数学杂志》2012,89(3):497-510
The hypercube network Q n has been proved to be one of the most popular interconnection networks. The n-dimensional locally twisted cube LTQ n is an important variant of Q n . One of the critical performance factors of an interconnection network is the diameter which determines the maximum communication time between any pair of processors. In this paper, we investigate the diameter variability problems arising from the addition and deletion of edges in LTQ n . We obtain three results in this paper: (1) for any integer n≥2, we find the least number of edges (denoted by ch ?(LTQ n )), whose deletion from LTQ n causes the diameter to increase, (2) for any integer n≥2, when ch ?(LTQ n ) edges are deleted, the diameter will increase by 1 and (3) for any integer n≥4, the least number of edges whose addition to LTQ n will decrease the diameter is at most 2 n?1. 相似文献
18.
Qiang-Sheng Hua Yuexuan Wang Dongxiao Yu Francis C.M. Lau 《Theoretical computer science》2009,410(38-40):3882-3892
Set multi-covering is a generalization of the set covering problem where each element may need to be covered more than once and thus some subset in the given family of subsets may be picked several times for minimizing the number of sets to satisfy the coverage requirement. In this paper, we propose a family of exact algorithms for the set multi-covering problem based on the inclusion–exclusion principle. The presented ESMC (Exact Set Multi-Covering) algorithm takes O*((2t)n) time and O*((t+1)n) space where t is the maximum value in the coverage requirement set (The O*(f(n)) notation omits a polylog(f(n)) factor). We also propose the other three exact algorithms through different tradeoffs of the time and space complexities. To the best of our knowledge, this present paper is the first one to give exact algorithms for the set multi-covering problem with nontrivial time and space complexities. This paper can also be regarded as a generalization of the exact algorithm for the set covering problem given in [A. Björklund, T. Husfeldt, M. Koivisto, Set partitioning via inclusion–exclusion, SIAM Journal on Computing, in: FOCS 2006 (in press, special issue)]. 相似文献
19.
We consider a recursive algorithm for constructing an ordered system of generators of a symmetric group of degree n. We show that the number of transpositions that form this system is O(n log22
n). This is only by a factor of log2
n greater in order than the lower bound on the number of transpositions in such a system. 相似文献
20.
The β-skeleton is a measure of the internal shape of a planar set of points. We get an entire spectrum of shapes by varying
the parameter β. For a fixed value of β, a β-skeleton is a geometric graph obtained by joining each pair of points whose β-neighborhood
is empty.
For β≥1, this neighborhood of a pair of points p
i
,p
j
is the interior of the intersection of two circles of radius , centered at the points (1−β/2)p
i
+(β/2)p
j
and (β/2)p
i
+(1−β/2)p
j
, respectively. For β∈(0,1], it is the interior of the intersection of two circles of radius , passing through p
i
and p
j
.
In this paper we present an output-sensitive algorithm for computing a β-skeleton in the metrics l
1 and l
∞ for any β≥2. This algorithm is in O(nlogn+k), where k is size of the output graph. The complexity of the previous best known algorithm is in O(n
5/2logn) [7].
Received April 26, 2000 相似文献