导读:本文包含了计算复杂性论文开题报告文献综述、选题提纲参考文献及外文文献翻译，主要关键词:复杂性,量子,算法,自动机,数据,组合,等式。
计算复杂性论文文献综述
王凯宁[1]（2019）在《量子机器学习与人工智能的实现——基于可计算性与计算复杂性的哲学分析》一文中研究指出量子机器学习是量子计算与机器学习交叉形成的新研究方向,其主要目标是利用量子特性实现对传统机器学习算法的加速。目前已经出现了不少有实际应用价值的量子机器学习算法,这些算法能通过降低计算的复杂性程度,在一些特定领域实现弱人工智能。从可计算性的视角来看,量子机器学习能完成非决定性计算,在理论上可以实现对意识结果的模拟,从而为强人工智能提供支持。(本文来源于《科学技术哲学研究》期刊2019年06期）
赵敬盈[2]（2019）在《几类半群的有限基问题和计算复杂性的研究》一文中研究指出令UT2(F)为域F上主对角线上元素为0,1的全体二阶上叁角矩阵在矩阵乘法下构成的半群;UTn(T)为热带半环T=R∪{-∞}上全体n阶上叁角矩阵在矩阵乘法下构成的半群;UT2(F)为域F上主对角线上元素为0,1,-1的全体二阶上叁角矩阵在矩阵乘法下构成的半群.本文给出判定对合半群是非有限基的一个充分条件,作为应用,证明了半群UT2(F)在伴随运算下的对合半群(UT2(F),*)是非有限基的;利用对合半群是非有限基的一个充分条件证明了热带半群UT2(T)在斜转置运算下的对合半群(UT2(T),D)是非有限基的,并证明了该对合半群(UT2(T),D)的等式检测问题和多项式非零问题都是多项式可解的;证明了半群UT2±(F2)与它的有限基的子半群UT2(F2)有相同的等式基,从而它们生成相同的簇.(本文来源于《兰州大学》期刊2019-05-01）
朱凯,毋国庆,吴理华,袁梦霆[3]（2019）在《有关时间自动机重置的若干问题的计算复杂性》一文中研究指出自动机的重置序列也称为同步序列,具有以下特性:有限自动机通过运行重置序列w,可从任意一个未知的或无法观测到的状态q0到达某个特定状态qw.这仅依赖于w,而与开始运行w时的状态q0无关.这一特性可用于部分可观察的复杂系统的自动恢复,而无需重启,甚至有时不能重启.基于此,重置问题自出现以来便得到关注和持续研究.最近几年,它被扩展到可以描述诸如分布式、嵌入式实时系统等复杂系统的无限状态模型上,比如时间自动机和寄存器自动机等.以时间自动机的重置问题的计算复杂性为研究对象,发现重置问题与可达性问题有着紧密的联系.主要贡献是:(1)利用时间自动机可达性问题的最新成果,完善完全的确定的时间自动机重置问题的计算复杂性结论;(2)对部分规约的确定的时间自动机,研究得出,即使在输入字母表大小减至2的情况下,其复杂性仍是PSPACE-完全的;特别地,在单时钟情况下是NLOGSPACE-完全的;(3)对完全的非确定的时间自动机,研究得出其Di-可重置问题(i=1,2,3)是不可判定的,其重置问题与非确定的寄存器自动机重置问题在指数时间可以相互归约,通过证明指数时间归约相对高复杂性类具有封闭性,利用非确定的寄存器自动机的结论得出单时钟的时间自动机的重置问题是Ackermann-完全的、限界的重置问题是NEXPTIME-完全的.这些复杂性结论,说明关于时间自动机的重置问题大都是难解的,一方面,为时间系统的可重置性的检测和求解奠定坚实的理论基础,另一方面,为以后寻找具有高效算法的特殊结构的时间系统(即具有高效算法的问题子类)给予理论指导.(本文来源于《软件学报》期刊2019年07期）
杨勇杰[4]（2019）在《浅析算法分析和计算复杂性理论研究方法》一文中研究指出近年来,我国数学领域的高速发展,使越来越多的人们认识到数学的重要性,这也使数学在各个领域中发挥着越来越重要的作用。该文浅要分析了算法及其计算复杂性,并将线性方程组中的LU分解的递归算法作为实例,以此分析算法的计算复杂性。希望能够为专家与学者在算法分析工作中提供一种科学的研究方法,进一步推动算法在各个领域中的应用。(本文来源于《科技资讯》期刊2019年05期）
罗磊,刘新旺,祝恩[5]（2018）在《围绕科学研究能力培养的研究生计算复杂性课程建设》一文中研究指出阐述了面向计算机科学与技术一级学科的研究生计算复杂性课程教学目标,根据该目标设计了先具体后抽象、面向科技论文结构的教学内容和方法,以及立足批判性阅读的论文分享教学环节,从而培养学生的综合研究能力。(本文来源于《计算机工程与科学》期刊2018年S1期）
余建军,吴春明[6]（2018）在《虚拟网映射问题的计算复杂性分析》一文中研究指出虚拟网映射是实现网络虚拟化的关键环节,其任务是在满足虚拟网构建约束的前提下,把虚拟网的虚拟节点和虚拟链路分别映射到底层物理网的节点和路径上。文中根据虚拟节点映射是否已知、物理网是否支持路径分割、物理节点是否支持重复映射等特征,对虚拟网映射问题进行分类,并针对一般网络拓扑模型和某些特殊网络拓扑模型完成各类虚拟网映射可行问题和优化问题的计算复杂性分析。(本文来源于《计算机科学》期刊2018年11期）
李培培,丁晓东[7]（2018）在《基于NP-完备理论的组合最优化及计算复杂性研究》一文中研究指出近年来,我国计算机科学得到了迅猛的发展,这也使人们提出许多理论试图深入揭示NP-完备理论所具备的密切关系,对基于NP-完备理论进行研究,将有助于推动计算机科学、运筹学、离散数学等相关学科的发展,进而帮助人们更好地利用NP-完备理论来处理实际问题。鉴于此,本文对基于NP-完备理论的组合最优化及计算复杂性进行深入的研究,以期能够为NP-完备理论的研究有一定贡献。(本文来源于《山西能源学院学报》期刊2018年04期）
高园[8]（2018）在《新型排序问题的计算复杂性研究》一文中研究指出排序是指在一定的约束条件下分配有限的资源于时间空间去完成多项任务使得一个或者多个目标达到理想或最优.排序的好坏直接影响着生产商成本的高低和利润的大小.因此,排序论对提高效率、科学决策、资源的开发与配置等方面都起到重要的作用.在排序论中,人们把任务统称为“工件”,而把资源统称为“机器”.本学位论文主要研究了若干新型排序问题的计算复杂性.在第二章中,我们研究了 GDD或ADD假设下的单机排序.在GDD假设下,工期按照EDD顺序进行排列,并按照工件完工时间的递增顺序连续分配给工件使得第i个工期分配给第i个完工的工件.而在ADD假设下,工期在分配给工件时是相互独立的.我们证明了两个历史遗留问题1|GDD|∑(Ei+Ti)和1|ADD|∑(Ei+Ti)都是常数界不可近似的.我们的证明也意味着这两个问题都是一元NP-困难的.此外,我们还证明了历史遗留问题1|GDD|∑wiTi是一元NP-困难的.在第叁章中,我们研究了单机上工件有位置限制的Pareto排序.首先,我们修正了历史文献中的推理错误.然后,对问题1｜σ[Jj]≤kj,prec|#(fmax,gmax),我们给出一个O(n4)-时间算法,其中“σ[Jj]≤ kj”表示工件Jj只能在前kj个位置上进行加工,“prec”表示工件的序约束限制.我们进一步证明了双代理排序问题l｜σ[Jj]≤kj,pre｜#(fmaxA,gmaxB)在O(nA3nB+nAnB3)时间内可解.在第四章中,我们研究了工件可自由下线的无界平行分批排序,其中可自由下线工件意味着每个工件的完工时间等于包含这个工件的批的开工时间与该工件的加工时间之和.首先,我们证明了问题p-batch(+∞)|drop-line,rj|Lmax是二元NP-困难的.此外,我们证明了,对每个γ∈{fmax,∑fj｝,问题p-batch(+∞)｜drop-line,rj|γ在伪多项式时间内可解,并且当工件实例有常数个不同的加工时间或常数个不同的到达时间时,该问题在多项式时间内可解.在第五章中,我们研究了工件有一致的到达时间和加工时间的无界平行分批排序.我们考虑两种类型的工件:批工件和自由下线工件.对批工件而言,每个工件的完工时间等于包含这个工件的批的完工时间.对双指标问题p-batch(+∞)|β*,(rj,pj)-agreeable|#(Cmax,fmax),其中 β*∈ {batch,drop-line},我们给出一个O(n3log（rmax+∑pj))-时间算法和一个O(n4)-时间算法.对单指标问题p-batch(+∞)|β*,(rj,pj)-agreeable|∑ wjUj,其中β*∈ {batch,drop-line},我们证明了该问题是二元NP-困难的,并给出了一个伪多项式时间算法和一个全多项式时间近似方案.在第六章中,我们研究了单台平行批机器上最小化最大完工时间的双代理排序,其中工件是批工件,有各自的到达时间和线性退化的加工时间.目标函数是,在代理B的最大完工时间不超过给定上界的条件下,最小化代理A的最大完工时间.Tang等人[144]对该排序模型给出了系统的研究.特别地,他们对下面四个问题给出了多项式时间算法.在第一个问题中,批容量无界且两个代理兼容.在第二个问题中,批容量有界,两个代理不兼容，A-工件有一个固定数目的正常加工时间,并且B-工件有一个相同的到达时间.在第叁个问题和第四个问题中,批容量有界,两个代理兼容,并且工件的到达时间和正常加工时间是一致的或者反一致的.在这一章中,我们证明了他们对这四个问题给出的算法都是无效的.我们对第一个问题给出了一个新的多项式时间算法并且证明了其他叁个问题都是二元NP-困难的.我们进一步对批容量有界,两个代理不兼容,并且A-工件和B-工件各有一个相同的到达时间的这种情形,给出了一个伪多项式时间算法.最后,我们对批容量无界且两个代理不兼容的情形,给出了一个强多项式时间算法.(本文来源于《郑州大学》期刊2018-03-01）
马秋武,吴力菡[9]（2018）在《试析优选论的计算复杂性问题》一文中研究指出文章首先介绍有关计算复杂性的相关概念,然后针对优选论是否具有计算难解的问题,概述各方面的论点,最后对优选论的算法等其他相关问题进行概括和总结。(本文来源于《同济大学学报(社会科学版)》期刊2018年01期）
苗东菁[10]（2016）在《数据一致性的计算复杂性理论和算法研究》一文中研究指出各应用领域信息量爆炸性地增长带来了大量的劣质数据。数据质量低劣经常导致灾难性后果,极大地限制了数据的正常使用。数据的劣质性概括性地表现为数据的不一致性、不准确性、不完全性和非时效性等等,而其中不一致数据是最典型的劣质数据。改善不一致性数据对于为提高数据可用性,确保大规模数据的正常使用有着十分重要的意义。然而已有的基于数据依赖规则描述数据一致性的处理方法发展还不够完善,并且这种方法本身还有着很多固有的缺陷,主要有以下几点:第一,一致性规则只能用于检测不一致错误,但并不能给出数据不一致程度的直观评估;第二,一致性规则不能指导修复,仅基于规则的自动方法不能保证完全地修复不一致数据;第叁,人工很难定义出足够的一致性规则以充分检测数据的一致性错误。本文对不一致关系数据的评估、修复、查询、规则挖掘等方面中的关键问题给出了一些列的计算复杂性和算法研究结果,分很好地决了上述问题,主要研究内容如下所述。(1)本文研究了数据一致性规则发现算法。为了克服挖掘严格的函数依赖和条件函数依赖的局限性,以及不好的松弛导致的大量无效冗余规则,本文在第二章研究了如何定义松弛规则以及如何从更一般的数据中挖掘他们。本文提出了从更一般的概率数据中挖掘出近似条件函数依赖的方法,由于概率数据可以视作一般数据的泛化,因此从概率数据中挖掘候选规则可以提高挖掘能力,适配更广泛的数据类型、提供专家用户更充分的参考规则,同理我们定义了近似条件函数依赖是松弛的,使得挖掘结果质量可控。在此基础上,本文研究了其在不确定数据中的置信概率的动态规划求解算法,以及候选依赖的概率下界来进行剪枝;给出了基于字典序的挖掘方法以及相应的剪枝策略;最后,在真实和合成的数据集上进行充分的实验以验证挖掘算法的可扩展性和剪枝策略的高效性,发现真实的挖掘结果,极大地提高了数据一致性的发现能力。(2)本文研究了数据一致性评估问题的计算复杂性和评估算法。为克服当前不能很好地评估数据一致性的缺陷,避免局部计数的失真问题,本文在第叁章提出通过最小元组删除集规模来评估数据的不一致程度。在此基础上研究了当给定规则集合的结构复杂程度对问题的计算复杂性的影响。本文证明了当Σ包含2条仅涉及3个属性的变量条件函数依赖、且每条元组最多仅涉及6个冲突对时,最小元组删除集问题仍然是NP完全;进而又证明了当给定3条仅涉及4个属性的变量条件函数依赖时,将最小删除集问题近似到1716是NP难的。本文给出了最小元组删除集问题的近优化的近似算法,可以达到2-12r的近似比,其中r为集合Σ中变量条件函数依赖个数,显然这是一个独立于数据量的、很好的近似比,因为条件函数依赖集合Σ通常规模远远小于数据量且固定。本文进一步说明了在UGC假设下,该近似比是近优化的,很难再将近似比降低一个与n无关的常数。本文通过实验验证了本文给出的评估算法具有非常好的准确度,验证了前述的理论结果。(3)本文研究了基于反馈的不一致数据修复问题计算复杂性和修复算法。对于不一致数据的修复,自动的修复方法具有严重的局限性,数据质量研究领域达成的共识是,引入人工反馈是得到高质量修复的一个重要的环节。然而已有的工作都基于叁个假设:人工提供的回答认为是正确的,且可以直接使用;人工提供的回答都可以直接向数据传播,无副作用;给定规则一定是正确的。这种假设在很多实际情况中是不合理的。因此,本文在第四章针对如何解决人工反馈的正确性保障问题,形式化地定义了两个判定问题,即约束规则定义的不一致数据中的视图删除和插入传播问题,同时研究了两个问题的计算复杂性和数据修复算法。本文研究了不一致数据上视图删除问题的复杂性,证明了如果查询为一个投影或者并查询时该问题为NP完全的,证明了当查询为一个合取查询时该问题是Σp2完全的,同时也证明了然而当查询是一个选择连接查询时,该问题的联合复杂性是LOGSPACE的,同时这个结论意味着一般的无副作用删除传播问题在组删除情况下,其联合复杂性也是在LOGSPACE的,这填补了一般的删除传播问题复杂性结果中的空白。本文提出了基于删除反馈的高效修复算法。本文也证明了不一致数据上视图插入问题在单插入与组插入、有限域与无限域等情况下的数据复杂性与联合复杂性结论。证明了对于不同类别的查询,该问题的数据和联合复杂性均位于PTIME与Σp2完全之间。不同于删除反馈,本文证明了不一致数据上视图插入问题会变得更难。本文在数据复杂性下分离出了一大类多项式可解情况,即无自连接的选择连接查询类sjf-SJ,提出了高效求解算法,通过实验验证了本文提出的修复算法极大提高了精确率和召回率。(4)本文研究了不一致数据查询处理算法。为了克服一致性查询回答方法对结果约束太过苛刻的不足,本文在第五章采用不确定概率数据来建模不一致数据,并通过可能世界的概率阈值来定义查询结果的质量,从而保证了在尽可能多给出带有自定义质量保证的查询结果。基于此,本文进一步研究了这种方法在广泛存在且研究较少的空间不一致数据上的应用,利用空间数据的地理相关性和局部性的特点来加速查询回答。以较为复杂的局部相关空间不一致数据为典型范例,给出带有概率阈值保证的频繁近邻查询结果。本文提出了一般的处理框架,包括对于概率质量函数的动态规划算法以及阈值过滤方法,很好地解决了应用现有的基于传统数据和基于不确定数据上的近邻查询算法直接处理这种查询会产生昂贵开销的问题,并在人工的和真实的数据上都进行充分地实验以验证算法的有效性和高效性。(本文来源于《哈尔滨工业大学》期刊2016-06-01）
计算复杂性论文开题报告
（1）论文研究背景及目的
此处内容要求：
首先简单简介论文所研究问题的基本概念和背景，再而简单明了地指出论文所要研究解决的具体问题，并提出你的论文准备的观点或解决方法。
写法范例：
令UT2(F)为域F上主对角线上元素为0,1的全体二阶上叁角矩阵在矩阵乘法下构成的半群;UTn(T)为热带半环T=R∪{-∞}上全体n阶上叁角矩阵在矩阵乘法下构成的半群;UT2(F)为域F上主对角线上元素为0,1,-1的全体二阶上叁角矩阵在矩阵乘法下构成的半群.本文给出判定对合半群是非有限基的一个充分条件,作为应用,证明了半群UT2(F)在伴随运算下的对合半群(UT2(F),*)是非有限基的;利用对合半群是非有限基的一个充分条件证明了热带半群UT2(T)在斜转置运算下的对合半群(UT2(T),D)是非有限基的,并证明了该对合半群(UT2(T),D)的等式检测问题和多项式非零问题都是多项式可解的;证明了半群UT2±(F2)与它的有限基的子半群UT2(F2)有相同的等式基,从而它们生成相同的簇.
（2）本文研究方法
调查法：该方法是有目的、有系统的搜集有关研究对象的具体信息。
观察法：用自己的感官和辅助工具直接观察研究对象从而得到有关信息。
实验法：通过主支变革、控制研究对象来发现与确认事物间的因果关系。
文献研究法：通过调查文献来获得资料，从而全面的、正确的了解掌握研究方法。
实证研究法：依据现有的科学理论和实践的需要提出设计。
定性分析法：对研究对象进行“质”的方面的研究，这个方法需要计算的数据较少。
定量分析法：通过具体的数字，使人们对研究对象的认识进一步精确化。
跨学科研究法：运用多学科的理论、方法和成果从整体上对某一课题进行研究。
功能分析法：这是社会科学用来分析社会现象的一种方法，从某一功能出发研究多个方面的影响。
模拟法：通过创设一个与原型相似的模型来间接研究原型某种特性的一种形容方法。
计算复杂性论文参考文献
[1].王凯宁.量子机器学习与人工智能的实现——基于可计算性与计算复杂性的哲学分析[J].科学技术哲学研究.2019
[2].赵敬盈.几类半群的有限基问题和计算复杂性的研究[D].兰州大学.2019
[3].朱凯,毋国庆,吴理华,袁梦霆.有关时间自动机重置的若干问题的计算复杂性[J].软件学报.2019
[4].杨勇杰.浅析算法分析和计算复杂性理论研究方法[J].科技资讯.2019
[5].罗磊,刘新旺,祝恩.围绕科学研究能力培养的研究生计算复杂性课程建设[J].计算机工程与科学.2018
[6].余建军,吴春明.虚拟网映射问题的计算复杂性分析[J].计算机科学.2018
[7].李培培,丁晓东.基于NP-完备理论的组合最优化及计算复杂性研究[J].山西能源学院学报.2018
[8].高园.新型排序问题的计算复杂性研究[D].郑州大学.2018
[9].马秋武,吴力菡.试析优选论的计算复杂性问题[J].同济大学学报(社会科学版).2018
[10].苗东菁.数据一致性的计算复杂性理论和算法研究[D].哈尔滨工业大学.2016
论文知识图
