共查询到20条相似文献,搜索用时 31 毫秒
1.
Sang-Eon Han 《Journal of Mathematical Imaging and Vision》2008,31(1):1-16
In order to discuss digital topological properties of a digital image (X,k), many recent papers have used the digital fundamental group and several digital topological invariants such as the k-linking number, the k-topological number, and so forth. Owing to some difficulties of an establishment of the multiplicative property of the digital
fundamental group, a k-homotopic thinning method can be essentially used in calculating the digital fundamental group of a digital product with
k-adjacency. More precisely, let
be a simple closed k
i
-curve with l
i
elements in
. For some k-adjacency of the digital product
which is a torus-like set, proceeding with the k-homotopic thinning of
, we obtain its k-homotopic thinning set denoted by DT
k
. Writing an algorithm for calculating the digital fundamental group of
, we investigate the k-fundamental group of
by the use of various properties of a digital covering (Z×Z,p
1×p
2,DT
k
), a strong k-deformation retract, and algebraic topological tools. Finally, we find the pseudo-multiplicative property (contrary to the
multiplicative property) of the digital fundamental group. This property can be used in classifying digital images from the
view points of both digital k-homotopy theory and mathematical morphology.
相似文献
Sang-Eon HanEmail: Email: |
2.
We investigate the arithmetic formula complexity of the elementary symmetric polynomials Skn{S^k_n} . We show that every multilinear homogeneous formula computing Skn{S^k_n} has size at least kW(logk)n{k^{\Omega(\log k)}n} , and that product-depth d multilinear homogeneous formulas for Skn{S^k_n} have size at least 2W(k1/d)n{2^{\Omega(k^{1/d})}n} . Since Sn2n{S^{n}_{2n}} has a multilinear formula of size O(n
2), we obtain a superpolynomial separation between multilinear and multilinear homogeneous formulas. We also show that Skn{S^k_n} can be computed by homogeneous formulas of size kO(logk)n{k^{O(\log k)}n} , answering a question of Nisan and Wigderson. Finally, we present a superpolynomial separation between monotone and non-monotone
formulas in the noncommutative setting, answering a question of Nisan. 相似文献
3.
V. R. Fatalov 《Problems of Information Transmission》2010,46(2):160-183
Let {ξ
k
}
k=0∞ be a sequence of i.i.d. real-valued random variables, and let g(x) be a continuous positive function. Under rather general conditions, we prove results on sharp asymptotics of the probabilities
$
P\left\{ {\frac{1}
{n}\sum\limits_{k = 0}^{n - 1} {g\left( {\xi _k } \right) < d} } \right\}
$
P\left\{ {\frac{1}
{n}\sum\limits_{k = 0}^{n - 1} {g\left( {\xi _k } \right) < d} } \right\}
, n → ∞, and also of their conditional versions. The results are obtained using a new method developed in the paper, namely,
the Laplace method for sojourn times of discrete-time Markov chains. We consider two examples: standard Gaussian random variables
with g(x) = |x|
p
, p > 0, and exponential random variables with g(x) = x for x ≥ 0. 相似文献
4.
We show that every languageL in the class ACC can be recognized by depth-two deterministic circuits with a symmetric-function gate at the root and
AND gates of fan-in log
O(1)
n at the leaves, or equivalently, there exist polynomialsp
n
(x
1
,..., x
n
) overZ of degree log
O(1)
n and with coefficients of magnitude
and functionsh
n
:Z{0,1} such that for eachn and eachx{0,1}
n
,XL
(x)
=h
n
(p
n
(x
1
,...,x
n
)). This improves an earlier result of Yao (1985). We also analyze and improve modulus-amplifying polynomials constructed by Toda (1991) and Yao (1985). 相似文献
5.
6.
DoRon B. Motter Jarrod A. Roy Igor L. Markov 《Annals of Mathematics and Artificial Intelligence》2005,44(1-2):121-156
Many algorithms for Boolean satisfiability (SAT) work within the framework of resolution as a proof system, and thus on unsatisfiable instances they can be viewed as attempting to find proofs by resolution. However it has been known since the 1980s that every resolution proof of the pigeonhole principle (PHPnm), suitably encoded as a CNF instance, includes exponentially many steps [18]. Therefore SAT solvers based upon the DLL procedure [12] or the DP procedure [13] must take exponential time. Polynomial-sized proofs of the pigeonhole principle exist for different proof systems, but general-purpose SAT solvers often remain confined to resolution. This result is in correlation with empirical evidence. Previously, we introduced the Compressed-BFS algorithm to solve the SAT decision problem. In an earlier work [27], an implementation of a Compressed-BFS algorithm empirically solved
instances in (n4) time. Here, we add to this claim, and show analytically that these instances are solvable in polynomial time by Compressed-BFS. Thus the class of tautologies efficiently provable by Compressed-BFS is different than that of any resolution-based procedure. We hope that the details of our complexity analysis shed some light on the proof system implied by Compressed-BFS. Our proof focuses on structural invariants within the compressed data structure that stores collections of sets of open clauses during the Compressed-BFS algorithm. We bound the size of this data structure, as well as the overall memory, by a polynomial. We then use this to show that the overall runtime is bounded by a polynomial. 相似文献
7.
LetC be a binary code of lengthn (i.e., a subset of {0, 1}
n
). TheCovering Radius of C is the smallest integerr such that each vector in {0, 1}
n
is at a distance at mostr from some code word. Our main result is that the decision problem associated with the Covering Radius of arbitrary binary
codes is NP-complete.
This result is established as follows. TheRadius of a binary codeC is the smallest integerr such thatC is contained in a radius-r ball of the Hamming metric space 〈{0, 1}
n
,d〉. It is known [K] that the problems of computing the Radius and the Covering Radius are equivalent. We show that the 3SAT
problem is polynomially reducible to the Radius decision problem.
A central tool in our reduction is a metrical characterization of the set ofdoubled vectors of length 2n: {v=(v
1
v
2 …v
2n
) | ∀i:v
2i
=v
2i−1}. We show that there is a setY ⊂ {0, 1}2n
such that for everyv ε {0, 1}2n
:v is doubled iffY is contained in the radius-n ball centered atv; moreover,Y can be constructed in time polynomial inn. 相似文献
8.
Hazem M. Bahig 《The Journal of supercomputing》2008,43(1):99-104
In this paper, we study the merging of two sorted arrays
and
on EREW PRAM with two restrictions: (1) The elements of two arrays are taken from the integer range [1,n], where n=Max(n
1,n
2). (2) The elements are taken from either uniform distribution or non-uniform distribution such that
, for 1≤i≤p (number of processors). We give a new optimal deterministic algorithm runs in
time using p processors on EREW PRAM. For
; the running time of the algorithm is O(log (g)
n) which is faster than the previous results, where log (g)
n=log log (g−1)
n for g>1 and log (1)
n=log n. We also extend the domain of input data to [1,n
k
], where k is a constant.
相似文献
Hazem M. BahigEmail: |
9.
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. 相似文献
10.
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}} 相似文献
11.
A. Ghizzetti 《Calcolo》1983,20(1):53-65
Summary A partition of the interval [x
0,x
n+1] inton+1 subintervals [x
i
,x
i+1] (i=0,1,...,n) is considered. A spline functionf(x)∈C
m
, which coincides with a polynomialp
i
(x)[p
i
(x
i
)=y
i
,p
i
(x
i+1)=y
i+1] of degreem+1 in [x
i
,x
i+1
], is introduced. Such a spline depends onm arbitrary constants. These constants are determined minimizing the integral
.
相似文献
12.
This paper presents a study on the convergence rate of two projection methods for solving the variational inequality problemh∈K, 〈C(h),f-h〉 ≥ 0, ∀f∈K, whereK is a closed convex subset of ℝ
n
,C is a mapping fromK to ℝ
n
and <.,.> denotes the inner product in ℝ
n
. The first method, proposed by Dafermos [6] for the case whenC is continuously differentiable and strongly monotone, generates a sequence{f
i
} inK which is geometrically convergent to the unique solutionh∈K of the variational inequality; i.e., there exists a constant λ≡]0,1[ such that for all i, ∥f
i+1
−h∥
G
≤λ ∥f
i
−h∥, whereG is a symmetric positive definite matrix and
∀f≡ℝ
n
. The second method, proposed by Bertsekas and Gafni [8] for the case whenK is polyhedral andC is of the formC=A
i
TA, whereA is anm×n matrix andT: ℝ
m
→ℝ
m
is Lipschitz continuous and strongly monotone, generates a sequence{f
i
} inK which converges to a solutionh≡K of the variational inequality and satisfies the following estimate: ∥f
i+1
−h∥
G
≤qβ
i
, whereq>0 and β≡]0,1[. We examine the dependence of the constants λ and β on the parameters of the methods and establish that, except
for particular cases, these constants do not assume those values which guarantee a rapid convergence of the methods.
This work was extracted from the degree thesis [9] (Supervisor: A Laratta), Dipartimento di Matematica, Università di Modena. 相似文献
13.
Ann argument function,f, is calledt-private if there exists a distributed protocol for computingf so that no coalition of at mostt processors can infer any additional information from the execution of the protocol. It is known that every function defined over a finite domain is [(n–1)/2]-private. The general question oft-privacy (fort[n/2]) is still unresolved.In this work, we relate the question of [n/2]-privacy for the class of symmetric functions of Boolean argumentsf: {0, 1}
n
{0, 1,...,n} to the structure of Hamming weights inf
–1(b) (b{0, 1, ...,n}). We show that iff is [n/2]-private, then every set of Hamming weightsf
–1(b) must be an arithmetic progression. For the class ofdense symmetric functions (defined in the sequel), we refine this to the following necessary and sufficient condition for [n/2]-privacy off: Every collection of such arithmetic progressions must yield non-identical remainders, when computed modulo the greatest common divisor of their differences. This condition is used to show that for dense symmetric functions, [n/2]-privacy impliesn-privacy. 相似文献
14.
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:
15.
Alexander A. Sherstov 《Computational Complexity》2010,19(1):135-150
We solve an open problem in communication complexity posed by Kushilevitz and Nisan (1997). Let R∈(f) and $D^\mu_\in
(f)$D^\mu_\in
(f) denote the randomized and μ-distributional communication complexities of f, respectively (∈ a small constant). Yao’s well-known minimax principle states that $R_{\in}(f) = max_\mu
\{D^\mu_\in(f)\}$R_{\in}(f) = max_\mu
\{D^\mu_\in(f)\}. Kushilevitz and Nisan (1997) ask whether this equality is approximately preserved if the maximum is taken over product distributions
only, rather than all distributions μ. We give a strong negative answer to this question. Specifically, we prove the existence
of a function f : {0, 1}n ×{0, 1}n ? {0, 1}f : \{0, 1\}^n \times \{0, 1\}^n \rightarrow \{0, 1\} for which maxμ product {Dm ? (f)} = Q(1) but R ? (f) = Q(n)\{D^\mu_\in (f)\} = \Theta(1) \,{\textrm but}\, R_{\in} (f) = \Theta(n). We also obtain an exponential separation between the statistical query dimension and signrank, solving a problem previously
posed by the author (2007). 相似文献
16.
P. Baratella 《Calcolo》1977,14(3):237-242
In this paper we study the remainder term of a quadrature formula of the form $$\int\limits_{ - 1}^1 {f(x)dx = A_n \left[ {f( - 1) + f(1)} \right] + C_n \sum\limits_{i = 1}^n {f(x_{n,i} ) + R_n \left[ f \right],} } $$ , withx x,i ∈-1,1, andR n [f]=0 whenf(x) is a polynomial of degree ≤n+3 ifn is even, or ≤n+2 ifn is odd. Such a formula exists only forn=1(1)11. It is shown that, iff(x)∈ C(h+1) [-1,1], (h=n+3 orn+2), thenR n [f]=f h+1 (τ)·± n . The values α n are given. 相似文献
17.
We show a new and constructive proof of the following language-theoretic result: for every context-free language L, there is a bounded context-free language L′⊆L which has the same Parikh (commutative) image as L. Bounded languages, introduced by Ginsburg and Spanier, are subsets of regular languages of the form w1*w2*?wm*w_{1}^{*}w_{2}^{*}\cdots w_{m}^{*} for some w
1,…,w
m
∈Σ
∗. In particular bounded context-free languages have nice structural and decidability properties. Our proof proceeds in two
parts. First, we give a new construction that shows that each context free language L has a subset L
N
that has the same Parikh image as L and that can be represented as a sequence of substitutions on a linear language. Second, we inductively construct a Parikh-equivalent
bounded context-free subset of L
N
. 相似文献
18.
Free binary decision diagrams (FBDDs) are graph-based data structures representing Boolean functions with the constraint (additional
to binary decision diagram) that each variable is tested at most once during the computation. The function EARn is the following Boolean function defined for n × n Boolean matrices: EARn(M) = 1 iff the matrix M contains two equal adjacent rows. We prove that each FBDD computing EARn has size at least
and we present a construction of such diagrams of size approximately
. 相似文献
19.
Paul E. Dunne 《Acta Informatica》1985,22(2):229-240
Summary The k-th threshold function, T
k
n
, is defined as:
where x
i{0,1} and the summation is arithmetic. We prove that any monotone network computing T
3/n(x
1,...,x
n) contains at least 2.5n-5.5 gates.This research was supported by the Science and Engineering Research Council of Great Britain, UK 相似文献
|