共查询到20条相似文献,搜索用时 765 毫秒
1.
We construct formulae that assume the value 1 when and only when at least k of their n variables assume the value 1, using only conjunction and disconjunction, and having (for any fixed k) only occurences of variables. 相似文献
2.
3.
4.
《Theoretical computer science》2002,284(2):199-206
We discuss the uniform computational complexity of the derivatives of C∞-functions in the model of Ko and Friedman (Ko, Complexity Theory of Real Functions, Birkhäuser, Basel, 1991; Ko, Friedman, Theor. Comput. Sci. 20 (1982) 323–352). We construct a polynomial time computable real function g∈C∞[−1,1] such that the sequence is not bounded by any recursive function. On the other hand, we show that if f∈C∞[−1,1] is polynomial time computable and the sequence of the derivatives of f is uniformly polynomially bounded, i.e., |f(n)(x)| is bounded by 2p(n) for all x∈[−1,1] for some polynomial p, then the sequence is uniformly polynomial time computable. 相似文献
5.
6.
Michael C. Loui 《Theoretical computer science》1981,15(3):311-320
Let L be a language recognized by a nondeterministic d-dimensional Turing machine with one worktape head of time complexity T(n). Then L can be recognized by a deterministic Turing machine of space complexity . The proof employs a generalization of crossing sequences. 相似文献
7.
Let L denote the nonscalar complexity in k(x1,…, xn). We prove . Using this we determine the complexity of single power sums, single elementary symmetric functions, the resultant and the discriminant as root functions, up to order of magnitude. Also we linearly reduce matrix inversion to computing the determinant. 相似文献
8.
John Jones 《Mathematics and computers in simulation》1983,25(6):489-492
The main purpose of this work is to establish necessary conditions and sufficient conditions for the existence of a solution of matrix equations whose coefficient matrices have elements belonging to the ring of polynomials in n variables with complex coefficients and the ring of rational functions a(z1,z2,…zn)b(z1,z2,…,zn)?1 with real coefficients and b(z1,z2,…,zn)≠0 for all (z1,z2,…,zn) in Rn. Results obtained are useful in multidimensional systems theory and elsewhere. 相似文献
9.
We construct a sequence of monotone Boolean functions hn :{0, 1}n→{0, 1}n, such that the monotone complexity of hn is of order . This result includes the largest known lower bound of this kind. Previously there were an bound for the Boolean matrix product, an bound for Boolean sums and an bound by the author for the same functions hn. This new lower bound is proved by new methods which probably will turn out to be useful also for other problems. 相似文献
10.
Roger D. Nussbaum 《Systems & Control Letters》1983,3(5):243-246
A.S. Morse has raised the following question: Do there exist differentiable functions with the property that for every nonzero real number λ and every (x0, y0) ∈ 2 the solution (x(t),y(t)) of , , , is defined for all t ? 0 and satisfies and y(t) is bounded on [0,∞)? We prove that the answer is yes, and we give explicit real analytic functions f and g which work. However, we prove that if f and g are restricted to be rational functions, the answer is no. 相似文献
11.
Bezier's method is one of the most famous in computational geometry. In his book Numerical control Bezier gives excellent expositions of the mathematical foundations of this method. In this paper a new expression of the functions {fn,i(u)} is obtained.Using this formula, we have not only derived some properties of the functions {fn,i(u)} (for instance and functions {fn,i(u)} increase strictly at [0, 1] etc) but also simplified systematically all the mathematical discussions about Bezier's method.Finally we have proved the plotting theorem completely by matrix calculation. 相似文献
12.
13.
14.
Every t(n)-time bounded RAM (assuming the logarithmic cost measure) can be simulated by a t(n)/log t(n)-space bounded Turing machine and every t(n)-time bounded Turing machine with d-dimensional tapes by a bounded machine, where n is the length of the input. A class of storage structures which generalizes multidimensional tapes is defined. Every t(n)-time bounded Turing machine whose storage structures are in can be simulated by a t(n) loglog t(n)/log t(n)-space bounded Turing machine. 相似文献
15.
We give a method, based on algebraic geometry, to show lower bounds for the complexity of polynomials with algebraic coefficients. Typical examples are polynomials with coefficients which are roots of unity, such as and where pj is the jth prime number.We apply the method also to systems of linear equations. 相似文献
16.
17.
Michael C. Loui 《Theoretical computer science》1982,21(2):145-161
For all d ? 1 and all e >d, every deterministic multihead e-dimensional Turing machine of time complexity T(n) can be simulated on-line by a deterministic multihead d-dimensional Turing machine in time O(T(n)1+1?d?1?(logT(n))0(1)). This simulation almost achieves the known lower bound on the time required. The simulation is interpreted in terms of dynamic embeddings among arrays with local access. 相似文献
18.
J.L. Brown 《Information Sciences》1977,12(2):93-103
A given deterministic signal x(.) is distorted by passing it through a linear time-invariant filter and also by subjecting it to the action of an instantaneous nonlinearity. The resulting time crosscorrelation of the two distorted versions of the original signal is expressed by the function , where x(.) is the given signal, k(.) is the nonnegative definite impulse response of the linear filter, and g(.) is the output-input characteristic of the zero-memory nonlinear device. The problem considered is that of determining conditions on the pair (x,g) such that R2(s) ? R2(0) for all s and any choice of nonnegative definite filter function k; the principal result is the formulation of a necessary and sufficient condition for R2 to have a global maximum at the origin. In particular, the peak value occurs at the origin if and only if is real and nonnegative for all ω ? 0, where Gx(.) and X(.) are the Fourier transforms of g[x(.)] and x(.), respectively. An equivalent condition is that the correlation function , previously studied by Richardson, be nonnegative definite.Several examples are given, and it is shown that, unlike the case for R1(.), monotonicity of g(.) is not a sufficient condition for R2(.) to have a global maximum at s = 0 independently of the choice of filter characteristic k. Certain extensions of these results are given for the case when x(.) is a Gaussian random input. 相似文献
19.
《Computers & Mathematics with Applications》2003,45(6-9):1113-1123
We study positive increasing solutions of the nonlinear difference equation where {an}, {bn} are positive real sequences for n ≥ 1, fR → R is continuous with uf(u) > 0 for u ≠ 0. A full characterization of limit behavior of all these solutions in terms of an, bn is established. Examples, showing the essential role of used hypotheses, are also included. The tools used are the Schauder fixed-point theorem and a comparison method based on the reciprocity principle. 相似文献
20.
A. Nozaki 《Journal of Computer and System Sciences》1979,19(3):309-315
The number of required deques for sorting all sequences of n items in a parallel or series network of deques is considered. It is shown that the optimal number of required deques is for a parallel network, while it is O(log n) for a series network. These orders, and O(log n), also remain valid for the networks of restricted deques. 相似文献