共查询到20条相似文献,搜索用时 15 毫秒
1.
We investigate the characterizations of effective randomness in terms
of Martin-Lof tests and martingales. First, we address a question of Ambos-Spies and
Kucera, who asked for a characterization of computable randomness in terms of
tests. We argue that computable randomness can be characterized in terms of Martin-Lof tests and effective probability distributions
on Cantor space. Second, we
show that the class of Martin-Lof random sequences coincides with the class of sequences
that are random with respect to computable martingale processes;
the latter randomness notion was introduced by
Hitchcock and Lutz. Third, we analyze the sequence of measures of the components of a universal Martin-Lof test. Kucera and
Slaman showed that any component of a universal Martin-Lof test defines a class of Martin-Lof random measure. Further,
since the sets in a Martin-Lof test are uniformly computably
enumerable, so is the corresponding sequence of measures. We prove an exact
converse and hence a characterization. For any uniformly computably enumerable
sequence r1, r2,... of reals such that each rn is Martin-Lof random and
less than 2-n there is a universal Martin-Lof test
U1, U2,... such that Un{0,1}∞ has measure rn. 相似文献
2.
Some Results on Classical Preferential Models 总被引:1,自引:0,他引:1
3.
设g(x)≤f(x)是定义在V(G)上的两个整数值函数,h(e)∈[0,1]是定义在图G的边集E(G)上的函数。令dGh(x)=移e∈Exh(e),其中Ex={xy:xy∈E(G)}。若对所有的x∈V(G)都有g(x)≤dGh(x)≤f(x)成立,称h是G的一个(g,f)-表示函数。Gh是图G的一个支撑子图使得E(Gh)={e:e∈E(G),h(e)≠0},则称Gh是G的一个分数(g,f)-因子。文章给出,若对V(G)中的任意两个顶点u和v,G-{u,v}有分数k-因子存在。则G有一个分数k-因子不含图G中任意给定的边e∈E(G);当G有分数1-因子F=Gh存在时,对任意e∈F,G-V(e)有分数k-因子存在,则G有分数k-因子。 相似文献
4.
We establish a 1-1 correspondence between Valiant's character theory of match-gate/matchcircuit [13] and his signature theory of planarmatchgate/matchgrid [15], thus unifying the two theories in expressibility. In [3], we established a complete characterization of general matchgates, in terms of a set of useful Grassmann-Plucker identities. The 1-1 correspondence established in this paper gives a corresponding set of identities which completely characterizes planar-matchgates and their signatures. Applying this characterization we prove some negative results for holographic algorithms. On the positive side, we also give a polynomial time algorithm for a simultaneous node-edge deletion problem, using holographic algorithms. Finally we give characterizations of symmetric signatures realizable in the Hadamard basis. 相似文献
5.
We consider hypotheses about nondeterministic computation that have been studied in different contexts and shown to have interesting
consequences:
We show that the NP-machine hypothesis is implied by each of the first two. Previously, no relationships were known among
these three hypotheses. Moreover, we unify previous work by showing that several derandomizations and circuit-size lower bounds
that are known to follow from the first two hypotheses also follow from the NP-machine hypothesis. In particular, the NP-machine
hypothesis becomes the weakest known uniform hardness hypothesis that derandomizes AM. We also consider UP versions of the
above hypotheses as well as related immunity and scaled dimension hypotheses.
相似文献
• | The measure hypothesis: NP does not have p-measure 0. |
• | The pseudo-NP hypothesis: there is an NP language that can be distinguished from any DTIME language by an NP refuter. |
• | The NP-machine hypothesis: there is an NP machine accepting 0* for which no -time machine can find infinitely many accepting computations. |
6.
针对Markov跳变系统,本文利用去随机化方法将随机跳变系统转化为包含转移速率信息的确定系统,并讨论系统在给定时间内的控制问题,将特定频段干扰信号的频率信息引入控制器设计,以确保系统满足有限频段性能指标;同时从时间的角度设计给定时间控制器,使系统状态轨迹在工艺要求的时间内受限运动.所提方案不仅从频率、时间的尺度对系统频域特性及暂态性能进行综合分析,还充分考虑模态跳变对整体系统性能的影响,为降低现有设计方法的保守性提供了新的思路.最后仿真示例验证了所提方法的有效性及优越性. 相似文献
7.
8.
关于离散空间中最优搜索策略的一些结果 总被引:2,自引:0,他引:2
研究关于N个位置的最优搜索问题.最优搜索问题是研究如何将用于搜索的资源(如时间等)分配到N个位置使得发现目标的概率为最大.以往人们在研究最优搜索问题时总是假设目标的分布函数是已知的,但实际情况往往不是这样.用拉格朗日算子理论来研究目标的分布函数是未知的情况下的最优搜索问题,得出了一系列新的结果,包括分布函数的近似方法和误差估计公式.最后给出了两个例子. 相似文献
9.
The area of derandomization attempts to provide efficient deterministic simulations of randomized algorithms in various algorithmic settings. Goldreich and Wigderson introduced a notion of “typically-correct” deterministic simulations, which are allowed to err on few inputs. In this paper, we further the study of typically-correct derandomization in two ways. 相似文献
10.
论文从拓扑学角度研究覆盖近似空间(U,C),提出了加细覆盖的概念,讨论了加细覆盖近似空间的约简问题;同时给出了对定义在加细覆盖近似空间上的模糊集进行上、下近似计算的一种计算方法,并讨论该算法的一些性质。 相似文献
11.
12.
Jean-Marc Vincent 《Discrete Event Dynamic Systems》1997,7(2):209-232
This paper deals with the asymptotic behavior of the stochastic dynamics of discrete event systems. In this paper we focus on a wide class of models arising in several fields and particularly in computer science. This class of models may be characterized by stochastic recurrence equations in K of the form T(n+1) =
n+1(T(n)) where
n
is a random operator monotone and 1—linear. We establish that the behaviour of the extremas of the process T(n) are linear. The results are an application of the sub-additive ergodic theorem of Kingman. We also give some stability properties of such sequences and a simple method of estimating the limit points. 相似文献
13.
14.
Long Quan Bill Triggs Bernard Mourrain 《Journal of Mathematical Imaging and Vision》2006,24(3):341-348
Methods for reconstruction and camera estimation from miminal data are often used to boot-strap robust (RANSAC and LMS) and
optimal (bundle adjustment) structure and motion estimates. Minimal methods are known for projective reconstruction from two
or more uncalibrated images, and for “5 point” relative orientation and Euclidean reconstruction from two calibrated parameters,
but we know of no efficient minimal method for three or more calibrated cameras except the uniqueness proof by Holt and Netravali.
We reformulate the problem of Euclidean reconstruction from minimal data of four points in three or more calibrated images,
and develop a random rational simulation method to show some new results on this problem. In addition to an alternative proof
of the uniqueness of the solutions in general cases, we further show that unknown coplanar configurations are not singular,
but the true solution is a double root. The solution from a known coplanar configuration is also generally unique. Some especially
symmetric point-camera configurations lead to multiple solutions, but only symmetry of points or the cameras gives a unique
solution. 相似文献
15.
公钥加密方案的匿名性(亦称公钥隐密性)与数据保密性同样都具有重要应用价值.文中首先建立关于公钥加密方案的两个通用的新概念,即相对匿名性和相对保密性.通过这些较弱的安全性概念,证明了关于公钥加密方案匿名性质的两类一般性结果.第一类结果建立了公钥加密方案的保密性与匿名性之间两个对偶式的普遍关系,即相对匿名性(相对保密性)连同保密性(匿名性)蕴涵匿名性(保密性);第二类结果给出两个典型的混合加密构造(即Fujisaki-Okamoto构造和Okamoto-Pointcheval构造(REACT))选择密文匿名的充分条件,这些条件仅包括特定意义上的相对匿名性质和其它一些自然的弱保密性要求.文中不仅用多个具体实例表明这些条件都是非常实用的判定准则,而且还进一步应用这些普遍结果,给出对某些具体公钥加密方案匿名性质的简化证明,并证明了著名的NESSIE方案PSEC-1/2/3的选择密文匿名性质. 相似文献
16.
Pythagorean fuzzy sets (PFSs), originally proposed by Yager (Yager, Abbasov. Int J Intell Syst 2013;28:436–452), are a new tool to deal with vagueness considering the membership grades are pairs satisfying the condition . As a generalized set, PFSs have close relationship with intuitionistic fuzzy sets (IFSs). PFSs can be reduced to IFSs satisfying the condition . However, the related operations of PFSs do not take different conditions into consideration. To better understand PFSs, we propose two operations: division and subtraction, and discuss their properties in detail. Then, based on Pythagorean fuzzy aggregation operators, their properties such as boundedness, idempotency, and monotonicity are investigated. Later, we develop a Pythagorean fuzzy superiority and inferiority ranking method to solve uncertainty multiple attribute group decision making problem. Finally, an illustrative example for evaluating the Internet stocks performance is given to verify the developed approach and to demonstrate its practicality and effectiveness. 相似文献
17.
The modedling clip of the PHIGS ISO Standard is mathematically analysed. The most important result of this analysis is the fact that the projective image of a modding clip body (that is a not necessarily bounded convex body in space) is simply the union of two convex bodies. Furthermore, it will also be proved that in some cases one of these two bodies is empty. This fact makes the implementation of the modelling clip fairly straightforward and makes it also possible to use all already existing results on clipping against general convex bodies without change. 相似文献
18.
把几种具有较高逼近精度的频域降阶模型用于控制系统设计,给出设计后的仿真结果.说明不仅应研究如何提高逼近精度,而且应研究降阶设计方法. 相似文献
19.
This paper shows that the working set parameter-real memory and real memory-fault rate anomalies mentioned by Franklin, Graham, and Gupta in [13] do occur in traces generated by real programs. The results of the detailed investigation of this anomalous behavior in four Fortran programs are presented. In some cases a drop of a factor of two in the average real-time memory allotment is observed when the window size is increased. In some instances a bigger real-time memory allotment means an order of magnitude increase in page faults. 相似文献
20.
关璐 《电脑与微电子技术》2012,(7):25-27
利用超图在新的公理体系下同构的定义,给出超图自同构群的定义,这与特殊的情形——图的自同构群的定义是相容的,并将图的自同构群的一些结论在超图中进行推广。 相似文献