Structural properties of oracle classes

Denote by the class of oracles relative to which (collapsing oracles), and by the class of oracles relative to which (separating oracles). We present structural results on and . Using a diagonalization argument, we show that neither nor is closed under disjoint union, also known as join. We show that this implies that neither nor is closed under union, intersection, or symmetric difference. Consequently , the first level of the extended low hierarchy, is not closed under join.     

Prediction and dimension

Given a set X of sequences over a finite alphabet, we investigate the following three quantities.

(i)

The feasible predictability of X is the highest success ratio that a polynomial-time randomized predictor can achieve on all sequences in X.

(ii)

The deterministic feasible predictability of X is the highest success ratio that a polynomial-time deterministic predictor can achieve on all sequences in X.

(iii)

The feasible dimension of X is the polynomial-time effectivization of the classical Hausdorff dimension (“fractal dimension”) of X.

Predictability is known to be stable in the sense that the feasible predictability of X∪Y is always the minimum of the feasible predictabilities of X and Y. We show that deterministic predictability also has this property if X and Y are computably presentable. We show that deterministic predictability coincides with predictability on singleton sets. Our main theorem states that the feasible dimension of X is bounded above by the maximum entropy of the predictability of X and bounded below by the segmented self-information of the predictability of X, and that these bounds are tight.     

Gales suffice for constructive dimension

Supergales, generalizations of supermartingales, have been used by Lutz (2002) to define the constructive dimensions of individual binary sequences. Here it is shown that gales, the corresponding generalizations of martingales, can be equivalently used to define constructive dimension.     

Martingale families and dimension in P

We introduce a new measure notion on small complexity classes (called F-measure), based on martingale families, that gets rid of some drawbacks of previous measure notions: it can be used to define dimension because martingale families can make money on all strings, and it yields random sequences with an equal frequency of 0’s and 1’s. On larger complexity classes ( and above), F-measure is equivalent to Lutz resource-bounded measure. As applications to F-measure, we answer a question raised in [E. Allender, M. Strauss, Measure on small complexity classes, with application for BPP, in: Proc. of the 35th Ann. IEEE Symp. on Found. of Comp. Sci., 1994, pp. 807–818] by improving their result to: for almost every language A decidable in subexponential time, . We show that almost all languages in  do not have small non-uniform complexity. We compare F-measure to previous notions and prove that martingale families are strictly stronger than Γ-measure [E. Allender, M. Strauss, Measure on small complexity classes, with application for BPP, in: Proc. of the 35th Ann. IEEE Symp. on Found. of Comp. Sci., 1994, pp. 807–818], we also discuss the limitations of martingale families concerning finite unions. We observe that all classes closed under polynomial many-one reductions have measure zero in  iff they have measure zero in . We use martingale families to introduce a natural generalization of Lutz resource-bounded dimension [J.H. Lutz, Dimension in complexity classes, in: Proceedings of the 15th Annual IEEE Conference on Computational Complexity, 2000, pp. 158–169] on , which meets the intuition behind Lutz’s notion. We show that -dimension lies between finite-state dimension and dimension on . We prove an analogue of a Theorem of Eggleston in , i.e. the class of languages whose characteristic sequence contains 1’s with frequency α, has dimension the Shannon entropy of α in .     

Base invariance of feasible dimension

Effective fractal dimensions were introduced by Lutz (2003) in order to study the dimensions of individual sequences and quantitatively analyze the structure of complexity classes. Interesting connections of effective dimensions with information theory were also found, implying that constructive dimension as well as polynomial-space dimension are invariant under base change while finite-state dimension is not.We consider the intermediate case, polynomial-time dimension, and prove that it is indeed invariant under base change by a nontrivial argument which is quite different from the Kolmogorov complexity ones used in the other cases.Polynomial-time dimension can be characterized in terms of prediction loss rate, entropy, and compression algorithms. Our result implies that in an asymptotic way each of these concepts is invariant under base change.A corollary of the main theorem is any polynomial-time dimension 1 number (which may be established in any base) is an absolutely normal number, providing an interesting source of absolute normality.     

Resource-bounded strong dimension versus resource-bounded category

Classically it is known that any set with packing dimension less than 1 is meager in the sense of Baire category. We establish a resource-bounded extension: if a class X has Δ-strong dimension less than 1, then X is Δ-meager. This has the applications of explaining some of Lutz's simultaneous Δ-meager, Δ-measure 0 results and providing a new proof of a Gu's strong dimension result on infinitely-often classes.     

AMexp?(NP∩coNP)/poly

In this note we show that AM_exp?(NP∩coNP)/poly, where AM_exp denotes the exponential version of the class AM. Since there are oracles relative to which AM_exp⊆P/poly, our result is an instance of very few nonrelativizable separation results.     

An oracle builder’s toolkit

We show how to use various notions of genericity as tools in oracle creation. In particular,

1. we give an abstract definition of genericity that encompasses a large collection of different generic notions;

2. we consider a new complexity class AWPP, which contains BQP (quantum polynomial time), and infer several strong collapses relative to -generics;

3. we show that under additional assumptions these collapses also occur relative to Cohen generics;

4. we show that relative to -generics, ULIN∩co-ULINDTIME(n^k) for any k, where ULIN is unambiguous linear time, despite the fact that UP(NP∩co-NP)P relative to these generics;

5. we show that there is an oracle relative to which NP/1∩co-NP/1(NP∩co-NP)/poly; and

6. we use a specialized notion of genericity to create an oracle relative to which

NP^BPPMA.

Relativized collapsing between BPP and PH under stringent oracle access

We propose a new model of stringent oracle access defined for a general complexity class. For example, when comparing the power of two machine models relative to some oracle set X, we restrict that machines of both types ask queries from the same segment of the set X. In particular, for investigating polynomial-time (or polynomial-size) computability, we propose polynomial stringency, bounding query length to any fixed polynomial of input length. Under such stringent oracle access, we show an oracle G such that BPP^G = PH^G.     

A new algorithm for computing the minimum Hausdorff distance between two point sets on a line under translation

To determine the similarity of two point sets is one of the major goals of pattern recognition and computer graphics. One widely studied similarity measure for point sets is the Hausdorff distance. So far, various computational methods have been proposed for computing the minimum Hausdorff distance. In this paper, we propose a new algorithm to compute the minimum Hausdorff distance between two point sets on a line under translation, which outperforms other existing algorithms in terms of efficiency despite its complexity of O((m+n)lg(m+n)), where m and n are the sizes of two point sets.     

Finite-state dimension

Classical Hausdorff dimension (sometimes called fractal dimension) was recently effectivized using gales (betting strategies that generalize martingales), thereby endowing various complexity classes with dimension structure and also defining the constructive dimensions of individual binary (infinite) sequences. In this paper we use gales computed by multi-account finite-state gamblers to develop the finite-state dimensions of sets of binary sequences and individual binary sequences. The theorem of Eggleston (Quart. J. Math. Oxford Ser. 20 (1949) 31–36) relating Hausdorff dimension to entropy is shown to hold for finite-state dimension, both in the space of all sequences and in the space of all rational sequences (binary expansions of rational numbers). Every rational sequence has finite-state dimension 0, but every rational number in [0,1] is the finite-state dimension of a sequence in the low-level complexity class AC₀. Our main theorem shows that the finite-state dimension of a sequence is precisely the infimum of all compression ratios achievable on the sequence by information-lossless finite-state compressors.     

Constructive dimension equals Kolmogorov complexity

We derive the coincidence of Lutz's constructive dimension and Kolmogorov complexity for sets of infinite strings from Levin's early result on the existence of an optimal left computable cylindrical semi-measure M via simple calculations.     

豪斯道夫微积分和分数阶微积分模型的分形分析

清晰解读豪斯道夫微积分和分数阶微积分阶数的分形维意义,并比较这2种微积分建模方法的区别与联系.这是首次清晰定量地导出分数阶微积分的分形几何基础.提供豪斯道夫导数模型描述历史依赖过程的几何解释,即初始时刻依赖性问题,并与分数阶导数模型对比.基于本文作者的早期工作,详细描述非欧几里得距离的豪斯道夫分形距离定义——豪斯道夫导数扩散方程的基本解就是基于该豪斯道夫分形距离.该基本解实质上就是目前广泛使用的伸展高斯分布和伸展指数衰减统计模型.     

基于Hausdorff距离的签字验证问题

签字验证是一种验证身份的重要方法，有着广泛的重要应用。Hausdorff距离是一种常用的距离度量，简单易行并且有效，研究了Hausdorff距离在汉字签字验证问题中的应用，同时研究了签字预处理过程中的角度矫正和汉字切分问题，在85人的签字数据上做了实验，识别率达到90％以上。     

基于Hausdorff度量的快速图象匹配算法

借助于计算机形态学的膨胀运算,文章提出了一种基于Hausdorff距离的快速图象匹配算法.Hausdorff距离相似性度量简化为膨胀和累加运算两个步骤,与传统的Hausdorff距离计算方法相比,具有简单、快速的特点.仿真结果验证了所提出算法的有效性.     

Line segment Hausdorff distance on face matching

A novel concept of line segment Hausdorff distance is proposed in this paper. Researchers apply Hausdorff distance to measure the similarity of two point sets. It is extended here to match two sets of line segments. The new approach has the advantage to incorporate structural and spatial information to compute the similarity. The added information can conceptually provide more and better distinctive capability for recognition. This would strengthen and enhance the matching process of similar objects such as faces. The proposed technique has been applied online segments generated from the edge maps of faces with encouraging result that supports the concept experimentally. The results also implicate that line segments could provide sufficient information for face recognition. This might imply a new way for face coding and recognition.