【摘 要】
：
A new model for the well-known problem, the satisfiablility problem of boolean formula (SAT), is introduced. Based on this model, some variants of SAT and their
【机 构】
：
Department of Computer Science
论文部分内容阅读
A new model for the well-known problem, the satisfiablility problem of boolean formula (SAT), is introduced. Based on this model, some variants of SAT and their properties are presented. Denote by NP the class of all languages which can be decided by a non-deterministic polynomial Turing machine and by P the class of all languages which can be decided by a deterministic polynomial-time Turing machine. This model also allows us to give another candidate for the natural problems in ((NP-NPC)-P), denoted as NPI, under the assumption P≠NP, where NPC represents NP-complete. It is proven that this candidate is not in NPC under P≠NP. While, it is indeed in NPI under some stronger but reasonable assumption, specifically, under the Exponential-Time Hypothesis (ETH). Thus we can partially solve this long standing important open problem.
其他文献
以三氯苯为原料,依此经过硝化、水解和催化加氢制得4,6-二氨基间苯二酚盐酸盐.在多聚磷酸中,此盐酸盐和对氨基苯甲酸缩合成标题化合物.分别对中间体的重结晶、缩合反应温度、
音乐是一种表演艺术,个性和共性成为表演艺术家不可替代的特点。带有独创性的个性和作品内涵的共性是在音乐表演中有着重要地位和作用的两个方面。
Music is a performing a
我国公司法将其调整对象明确限定为有限责任公司和股份有限公司。两者均属于企业法人,股东承担的都是有限责任,公司有独立的法律人格。有限公司因有合理的内部管理、良好的法
随着现代科学和技术的不断进步,环境的污染和破坏问题也日趋严重.为了更好的保护我国的资源环境,国内关于环境犯罪危险犯立法的呼声也越来越高,因此,加强对单位环境犯罪危险
是一部综合性的法律,它既规定了立法目的、基本原则、管理体制、基本政策、还对动物进行分类和分环节管理.分类管理包括:将动物分为野生动物、农场动物、食用动物、宠物动物
绿色电力与绿色能源是能源法及能源产业发展中的两个重要范畴,但是二者内涵与外延并未在各国的法律政策中得到明确的揭示.本文阐述了绿色电力与绿色能源法律范畴的应有之义,
中国已签署的国际反酷刑公约明确表明了我国反酷刑的严正立场,但目前对酷刑的范围尚未达成统一共识,有鉴于此,笔者从酷刑的概念分析出发,对当代中国的酷刑范围做出了界定,以
利用一种新颖的催化生长方法,在生长BN纳米管的过程中直接引入F原子,获得了均匀F掺杂的BN纳米管.高分辨透射电子显微镜研究表明,构成BN纳米管的六元环由于F掺杂而被严重扭曲,
从夸克-反夸克通过介子场耦合的模型出发研究了(ΩN)LST是否存在束缚态的问题. 计算表明当考虑了s(s)湮没为K*介子的机制后,(Ω)02(1)/(2)是有可能形成结合能较大的束缚态.
A class of efficient parallel multivalue hybrid methods for stiff differential equations are presented,which are all extremely stable at infinity, A-stable for