【摘 要】
：
对于给定的距离参数ε,性质测试算法A需以高概率正确地区分给定的对象具备预定性质Π与ε-远离性质Π。若存在Π的测试算法A满足其询问复杂性独立于规模参数n,则称Π是可测的
【基金项目】
：
国家自然科学基金（61262006）,贵州省研究生创新基金（2010005）资助
论文部分内容阅读
对于给定的距离参数ε,性质测试算法A需以高概率正确地区分给定的对象具备预定性质Π与ε-远离性质Π。若存在Π的测试算法A满足其询问复杂性独立于规模参数n,则称Π是可测的。设H是一个图,性质H-free为不含H-子图的图所构成的集合。在有界度模型中,Goldreich与Ron证明了对任意连通图H,性质H-free是可测的[9]。在邻接矩阵模型中,证明了对任意图H,不管其连通与否,性质H-free是可测的。
其他文献
基/副版本技术是实现实时分布式系统容错的一个重要手段。提出了一种异构分布式混合型容错模型,该模型与传统的异构分布式实时调度模型相比同时考虑了周期和非周期调度任务。
在LTE系统中,动态调度对提高MBMS业务资源利用效率具有重要的理论与实际意义,而动态调度信息的设计亦是其中重要的一环。在详细讨论现有DSI设计方案存在的问题及其对MBMS业务
为了满足网络终端用户对网页噪音的过滤需求,提出一种面向终端用户的动态模板网页过滤系统模型,它基于模板并利用用户反馈自动进化过滤系统。设计了模板生成算法,模拟实验验
由于因果图的经典推理的计算复杂度是NP难的,因此其不便于推广和使用。基于因果图理论和MonteCarlo思想,提出了基于抽样的A-R Sampling和重要性抽样的因果图仿真推理算法。在
基于离散对数和秘密共享思想,提出一个高效的（t,n）门限群签名方案。份额分配中心DC（Distribution Center）以自选份额的形式与群中成员共享签名密钥。SC（Signature Combiner）对收到
Web服务合成的相容性是服务合成研究领域的重要问题。相容性分析需要考虑异步交互的服务合成环境。用形式化的分析方法为Web服务的合成建模,给出服务合成满足相容性要求的限
为了能够对敏捷开发项目进行有效的工作量估算,提出了一种基于BP神经网络的工作量估算模型。考虑到数据集中存在的一些噪声数据以及错误数据,并且软件开发工作量与其影响因子
以网格用户管理的用户状态与活动为研究内容,首先介绍了用户状态与活动在用户管理层次结构中的位置和作用,提出了一种基于元状态和子状态的用户状态图,给出了每个元状态的分
基于齐次泊松点过程的节点分布模型,在不同的衰落信道模型下推导了网络无孤立点概率的闭型表达式,用作网络连通概率的上界。特别分析了对数正态阴影衰落和瑞利衰落信道的相关