【摘 要】
：
We consider a regular random (k, s)-SAT problem.We show that for all k exceeding an absolute constant k0, with the clause density αureq > 2klog2-klog2/2 + εk, there is no satisfying assignments w.h.p.
【机 构】
：
College of Computer Science and Technology,Guizhou University,Guiyang (550025),China;Department of M
【出 处】
：
2015全国理论计算机科学学术年会
论文部分内容阅读
We consider a regular random (k, s)-SAT problem.We show that for all k exceeding an absolute constant k0, with the clause density αureq > 2klog2-klog2/2 + εk, there is no satisfying assignments w.h.p.To the best of our knowledge, it is below the current best known upper bound 2klog2 + εk.The proof directly employs ideas from the 1RSB cavity method and the Survey Propagation calculations.Furthermore, this bound is also blow the asymptotic bound of the uni%rm k-SAT problem, which is known as 2klog 2 (log 2 + 1)/2 + ok(1).Thus, it explains why the regular random (k, s)-SAT instances are computationally harder than the uniform k-SAT generally.
其他文献
以兰纳素染料三原色对羊毛散纤维进行染色,通过改变工艺条件,对比染色后织物的各项性能,探索了最适合羊毛染色的工艺条件和参数.兰纳素染料染液pH应控制在4～5;在85℃、98℃、100℃下都可以进行染色;可适当加入元明粉,但用量应控制在5％(owf)以下;加入1％～2％的Albegal B可以同时起到提高上染速率和匀染的作用;中性条件下固色即可.以溴代丙烯酰胺为活性基的兰纳素染料三原色拥有较好的配伍性
对不同细度的莱卡包芯纱、涤纶包芯纱,在小样织机上采用三种不同纬密进行无纬织造,纱线表面受到摩擦后,对纱线断裂强力、断裂伸长率、断裂强力下降率、断裂伸长率下降率以及纱线外观形态进行测试分新.实验结果得到,包芯纱断裂强力随纬纱密度增加而减小,纱线强力降低率逐渐增大;纱线断裂伸长率降低率随着纬密增加而增大.随着纬密增加,经过摩擦后,纱线的外包纤维变得松散,纱线紧密度降低,毛羽增加.对于相同线密度的包芯纱
研究了以16tex、涤纶、凯斯林、粘胶、毛这四种纤维混纺纱,混纺比60/10/15/15/为代表产品的差别化涤粘毛多组份混纺纱线的生产工艺流程、工艺参数,原料选配;通过功能性阳离子改性涤纶、凯斯林、粘胶这三种纤维在清花工序预先进行混合成卷,用特殊的装置将特殊定制的精梳毛条在梳棉机后与之同时喂入混合,经并条、粗纱、细纱纺成纱线.通过小试、中试、批量生产过程中,对纤维内在指标的优选、对各道生产工序工艺
为了探索青椒适宜的贮藏温度,以园丰4号青椒为试材,从青椒贮藏期果实的呼吸强度、含水率、可溶性固形物、总糖、可滴定酸及Vc等各项生理生化指标着手,研究了六个不同贮藏温度(1℃、5℃、7℃、10℃、13℃)对青椒贮藏期品质的影响.结果表明,(1)青椒的冰点温度在-2℃～-3℃之间;(2)1℃贮藏的青椒易产生冷害现象;(3)5℃贮藏温度可降低青椒的呼吸强度,抑制青椒失水萎蔫、腐烂,并可减缓青椒果实整个贮
为建立鲜切蔬菜的货架期预测模型,在冰温储藏下,通过正交设计确定了菠菜鲜切处理的最佳方案为用75mg/LCLO2水溶液、0.5％NaCl溶液分别浸泡10min后,PVDC保鲜膜包装.通过对鲜切菠菜相关理化指标、菌落总数的测定及感官评价,跟踪样品品质随时间、温度的变化关系.结果表明,菠菜叶绿素含量随着贮藏时间的延长分别呈现出逐渐升高和降低的趋势.随着贮藏温度的升高,菠菜相关的各品质指标变化率也增大,且
为了探明猴头菇褐变机制并抑制褐变,研究了柠檬酸处理和贮藏温度对猴头菇褐变度、总酚含量、多酚氧化酶(PPO)活性、过氧化物酶(POD)活性的影响.结果表明,猴头菇在(15±0.5)℃条件下贮藏褐变严重,而(1±0.5)℃下贮藏能有效抑制其褐变,柠檬酸处理后在(15±0.5)℃条件下贮藏依然褐变严重.总酚含量和PPO活性、POD活性与猴头菇褐变相关,但不是褐变的诱发原因.
In this paper, we restudy busy beaver problem that is defined by Tibor Rado in 1962.Based on his work, we describe four decision problems-busy beaver problerr, max shifter problem, halting empty tape
In this paper, a novel approach for initializing clustering centers of K-Means algorithm is presented.This method is based on the variance of dimension, which is used as keyword to make a full permuta
Kidney exchange programs have been established in several countries to organize kidney exchanges between incompatible patient-donor pairs.The core of these programs are algorithms to solve kidney exch
Till now, the types of attacks for cryptographic device are usually distinguished as leakage and tampering attacks respectively.The former, also known as side-channel attacks, is described that when r