|

楼主 |
发表于 2011-8-5 06:59
|
显示全部楼层
[注意][原创]文明上网,从源头做起!
下面引用由任在深在 2011/08/03 00:02pm 发表的内容:
中华数学
天圆地方勾股玄,
中华古学最璀璨,
华夏子孙多豪迈,
... 转摘:
NP就是Non-deterministic Polynomial的问题,也即是多项式复杂程度的非确定性问题。 什么是非确定性问题呢?有些计算问题是确定性的,比如加减乘除之类,你只要按照公式推导,按部就班一步步来,就可以得到结果。但是,有些问题是无法按部就班直接地计算出来。
比如,找大质数的问题。
有没有一个公式,你一套公式,就可以一步步推算出来,下一个质数应该是多少呢?这样的公式是没有的。
再比如,大的合数分解质因数的问题,有没有一个公式,把合数代进去,就直接可以算出,它的因子各自是多少?也没有这样的公式。 这种问题的答案,是无法直接计算得到的,只能通过间接的“猜算”来得到结果。这也就是非确定性问题。而这些问题的通常有个算法,它不能直接告诉你答案是什么,但可以告诉你,某个可能的结果是正确的答案还是错误的。
这个可以告诉你“猜算”的答案正确与否的算法,假如可以在多项式时间内算出来,就叫做多项式非确定性问题。而如果这个问题的所有可能答案,都是可以在多项式时间内进行正确与否的验算的话,就叫完全多项式非确定问题。 完全多项式非确定性问题可以用穷举法得到答案,一个个检验下去,最终便能得到结果。但是这样算法的复杂程度,是指数关系,因此计算的时间随问题的复杂程度成指数的增长,很快便变得不可计算了。
人们发现,所有的完全多项式非确定性问题,都可以转换为一类叫做满足性问题的逻辑运算问题。既然这类问题的所有可能答案,都可以在多项式时间内计算,人们於是就猜想,是否这类问题,存在一个确定性算法,可以在指数 时间内,直接算出或是搜寻出正确的答案呢?
这就是著名的NP=P?的猜想。
二〇一一年八月五日星期五
[br][br]-=-=-=-=- 以下内容由 changbaoyu 在 时添加 -=-=-=-=-
: 精确零知识证明系统研究
【英文题名】 A Study of Precise Zero-Knowledge
【作者】 丁宁;
【导师】 卿斯汉; 谷大武;
【关键词】 零知识证明; 精确零知识; 并发零知识; 知识证明; 交互证明与论证; 有界并发; 密码学; 计算复杂性;
【英文关键词】 zero-knowledge proofs; precise zero-knowledge; concurrent zero-knowledge; proofs of knowledge; interactive proofs and arguments; bounded concurrency; cryptography; computational complexity;
【中文摘要】 零知识证明是当今密码学中一个令人着迷的领域,它在现代密码学中有着极广的应用。零知识证明具有两点看起来相互矛盾的性质,一方面它能使有效的验证者能够接受某个正确论断,另一方面验证者却不能从该证明中学到任何新知识。在传统定义中,零知识性是指多项式时间验证者在交互中的视能在多项式时间内被重构。然而,一些文献指出零知识的这种传统定义是不精确的。最近一些研究者提出一称为精确零知识的新概念,该概念的引入动机是将传统零知识的定义精确化。一个证明称之为是精确零知识的,是指任何验证者在交互中的视都能被模拟器在几乎相同的时间内重构。可见,精确零知识的概念对零知识性的刻画非常得精细。而且,一些研究者们又进一步将这个概念从单机环境下推广至并发环境,提出了精确并发零知识的概念。 在本文中,我们考察了精确零知识研究的以下方面,包括具有良好性质的精确有界并发零知识协议的构造、精确零知识协议的通信复杂性、精确零知识协议的顺序合成以及如何提出新的刻画精确模拟的方法等。在第一个方面,我们试问对于任意NP语言是否能够构造具有较低轮复杂性的精确有界并发零知识协议?对于任意NP语言是否能够构造出精确有界并发零知识证明?在第二个方面,我...
【英文摘要】 Zero-knowledge proofs are a fascinating notion and have extremely wideapplications in modern cryptography. This notion reveals two seemingly para-doxical properties, i.e., a zero-knowledge proof can convince an effcient verifierto accept a valid assertion but it cannot learn anything more from the proof. Theproperty of zero-knowledge is captured by the idea that the view of polynomial-time verifiers in interaction can be reconstructed still in polynomial-time. So itcan be seen that zero-knowledge is f...
【更新日期】 2010-03-03
|
|