【摘 要】
：
植入团问题是平均情况复杂性中的一个中心问题。在植入团问题中,给定输入为一个随机图,其中植入了一个大小为k(n)的团,我们需要把这个团找出来;所谓的植入便是随机选取k(n)个
论文部分内容阅读
植入团问题是平均情况复杂性中的一个中心问题。在植入团问题中,给定输入为一个随机图,其中植入了一个大小为k(n)的团,我们需要把这个团找出来;所谓的植入便是随机选取k(n)个节点作为植入团中的节点,然后强制性的把这些节点间的边都连上。本文将植入团模型g(n,1/2,k(n))扩展为g(n,p(n),k(n)),并提出了边概率低的条件t(n)=o(logn)。在扩展的模型下,证明了经典结论的推广,得到植入团问题的通用的准多项式时间算法。针对边概率低的条件,证明了存在多项式时间随机算法以很大概率找到一个大小为c(?)=o(?)的植入团。初步研究了植入团问题的AC0[q]电路下界问题,找出了 Razborov-Smolensky方法和植入团问题之间的不兼容处,提出了将来可能的研究方向。
其他文献
太赫兹波是指0.1 THz到10 THz频带内的电磁波,它处于从宏观经典理论到微量子论以及从电子学到光子学的过渡区域。太赫兹波具有卓越的物理特性,已经在医疗、安检等领域广泛使
随着大数据技术的不断发展,人们探索了许多用于挖掘这些数据的算法。但是它们大多局限于挖掘数据中的关联关系,而没有深入理解数据中的因果关系,所以常常会导致一些错误的结
不可否认的是,尽管网络控制系统有诸多优点,但存在各种不确定影响因素,如外部环境中的随机干扰,内部环境中的网络时延、数据包丢失、网络攻击等。这些因素会导致系统性能的下
TiC和VC具有耐高温、抗腐蚀、硬度高且热稳定性良好等性能,因而在诸多领域获得了广泛应用。已知通过机械合金化(MA)可成功制备具有碳空位缺陷的TiC_x,空位的存在大大降低了烧结温度。本文利用MA的方法制备同TiC_x具有相同晶体结构的VC_x(0.4≤x≤0.6)纳米粉末。并将VC_x粉末进行放电等离子烧结,得到机械性能优异的VC_x烧结体。首先通过第一性原理计算,研究了VC_x的相稳定性随C含
随着环境污染和能源短缺问题的日益严峻,社会更加关注可再生清洁能源的利用,政企投入不断加大。近年来太阳能、风能和潮汐能等清洁能源逐渐进入能源市场。但未来几十年内石油、天然气、煤炭等化石能源依然会占据能源市场的主要地位。因此,提高化石能源热能转换效率,回收低品位余废热等节能减排技术受到了重视。热电转换是一种利用半导体材料的热电效应实现热能与电能直接转换的绿色能源技术。在工业余废热回收、节能减排、环境保
磁制冷技术是基于材料磁热效应的一种绿色环保型制冷技术。近年来,Gd-基过渡金属氧化物因具有巨大的磁热效应而受到广泛的关注。本论文合成了Gd-基材料GdFeTeO_6和GdFeTiO_5,并对其结构、磁性以及磁热效应进行了研究。主要内容如下:1.概述了磁制冷技术的发展背景、磁热效应的基本研究方法、稀土过渡金属材料的磁性质以及研究现状。简要介绍了高温固相反应法、超导量子干涉磁强计(SQUID)和脉冲强
直流无刷电机(英文Brushless DC Motor,简称BLDCM)使用定子绕组、转子磁铁取代有刷电机的定子磁铁、转子绕组,摒弃了电刷结构,大大延长了电机的使用寿命。它不但拥有直流电机
太阳风-磁层耦合过程是空间天气领域中十分重要的一个部分,也是被广泛关注的方向之一,其过程十分复杂,太阳活动可以通过该过程直接影响地球的空间环境。在这个过程中,超声速太阳风碰到地球磁层障碍物时形成弓激波,弓激波是十分重要的一个分界面,当卫星穿过弓激波时,其所处的环境会发生明显的变化,在灾害性空间天气事件下会给卫星带来极大的伤害,所以研究弓激波的位型对空间天气预报预警和卫星的运行环境及条件监测有着十分
社区养老设施公建民营运行机制的研究,是基于人口老龄化趋势加剧、社区养老设施公建民营实际运行乱的现实问题下提出的。社区养老设施公建民营是未来一定时期内养老服务体系发展的一个方向。研究上海市社区养老设施公建民营运行机制及其特色,对于积极应对人口老龄化、推广社区养老设施公建民营、实现养老服务公益定位、保基本生活以及满足新时代下新需求、新水平、新期待的民生建设具有重要的理论和现实意义。本研究针对上海市社区
锂离子电池因为其具有可充电性、能量密度大、方便携带和环境友好等优点,得到了广泛的研究与应用。目前,商业化的锂离子电池采用石墨作为负极材料,其理论比容量只有372 mAh g-1,已经难以满足现代电子产品发展的需求。自从2000年J-M.Tarascon等人报道了高容量的过渡金属氧化物负极材料以来,过渡金属氧化物材料得到了世界范围内科研人员的广泛关注。采用溶胶凝胶法合成了纳米尺寸的纯相Cu1.3Mn