百度作业网请问数学中P与NP是什么题（具体些）
来源：学生作业帮 编辑：百度作业网作业帮 分类：数学作业 时间：2024/05/29 18:41:54
请问数学中P与NP是什么题（具体些）
P/NP问题是在理论信息学中计算复杂度理论领域里至今没有解决的问题,它被“克雷数学研究所”（Clay Mathematics Institute,简称CMI）在千禧年大奖难题中收录.P/NP问题中包含了复杂度类P与NP的关系.1971年史提芬·古克(Stephen A.Cook) 和 Leonid Levin 相对独立的提出了下面的问题,即是否两个复杂度类P和NP是恒等的（P=NP?
复杂度类P包含所有那些可以由一个确定型图灵机在多项式表达的时间内解决的问题；类NP由所有其肯定解可以在给定正确信息的多项式时间内验证的决定问题组成,或者等效的说,那些解可以在非确定图灵机上在多项式时间内找出的问题的集合.很可能,计算理论最大的未解决问题就是关于这两类的关系的:.
更正式一些,一个决定问题是一个取一些字符串为输入并要求输出为是或否的问题.若有一个算法（譬如图灵机,或一个LISP或Pascal的程序并有无限的内存）能够在最多nk步内对一个串长度为n的输入给出正确答案,其中k是某个不依赖于输入串的常数,则我们称该问题可以在多项式时间内解决,并且将它置入类P.直观的讲,我们将P中的问题视为可以较快解决的问题.
现在假设有一个算法A(w,C)取两个参数,一个串w,也就是我们的决定问题的输入串,而另一个串C是“建议证明”,并且使得A在最多nk步之内产生“是/否”答案（其中n是w的长度而k不依赖于w）.进一步假设
w是一个答案为“是”的例子,当且仅当,存在C使得A(w,C)返回“是”.
则我们称这个问题可以在非决定性多项式时间内解决,且将它放入NP类.我们把算法A作为一个所建议的证明的检验器,它运行足够快.（注意缩写NP代表“Non-deterministic（非确定性）Polynomial（多项式）”而不是代表“Non-Polynomial（非多项式）.）
复杂度类P包含所有那些可以由一个确定型图灵机在多项式表达的时间内解决的问题；类NP由所有其肯定解可以在给定正确信息的多项式时间内验证的决定问题组成,或者等效的说,那些解可以在非确定图灵机上在多项式时间内找出的问题的集合.很可能,计算理论最大的未解决问题就是关于这两类的关系的:.
更正式一些,一个决定问题是一个取一些字符串为输入并要求输出为是或否的问题.若有一个算法（譬如图灵机,或一个LISP或Pascal的程序并有无限的内存）能够在最多nk步内对一个串长度为n的输入给出正确答案,其中k是某个不依赖于输入串的常数,则我们称该问题可以在多项式时间内解决,并且将它置入类P.直观的讲,我们将P中的问题视为可以较快解决的问题.
现在假设有一个算法A(w,C)取两个参数,一个串w,也就是我们的决定问题的输入串,而另一个串C是“建议证明”,并且使得A在最多nk步之内产生“是/否”答案（其中n是w的长度而k不依赖于w）.进一步假设
w是一个答案为“是”的例子,当且仅当,存在C使得A(w,C)返回“是”.
则我们称这个问题可以在非决定性多项式时间内解决,且将它放入NP类.我们把算法A作为一个所建议的证明的检验器,它运行足够快.（注意缩写NP代表“Non-deterministic（非确定性）Polynomial（多项式）”而不是代表“Non-Polynomial（非多项式）.）
请问数学中P与NP是什么题（具体些）
请问数学中“大化小与小化大”具体含义和口诀是什么
概率泊松定理的证明概率与数理统计中该定理的证明,即n->无穷大时二项分布(n,p)即参数np的泊松分布,请写出具体求极限
世界七大难题p与np问题解决了吗?
请问自动档汽车中,P,R,N,D,3,2,1档具体作用是什么?
一道高二数学基础题P是椭圆上任意一点,请问P与焦点F1连线长度的范围是什么?麻烦帮忙解答一下,谢谢了!
请问生化废水处理系统中BOD：N：P怎么计算,进水BOD=300mg/L,水量700方每天,每天NP补加量
请问在数学中,以下两个符号是什么（与取整有关）
英语语法中 S=NP+VP是什么的缩写
如图:平行四边形ABCD中MN // AC,分别交AB,BC,与DA延长线、DC延长线于点P、Q、M、N 说明MQ=NP
NP-EGTA是什么物质
关于世界七大数学难题什么是P和NP问题的内容