全部 标题 作者
关键词 摘要

OALib Journal期刊
ISSN: 2333-9721
费用:99美元

查看量下载量

相关文章

更多...

Remarks on AKS Primality Testing Algorithm and A Flaw in the Definition of P

Full-Text   Cite this paper   Add to My Lib

Abstract:

We remark that the AKS primality testing algorithm [Annals of Mathematics 160 (2), 2004] needs about 1,000,000,000 G (gigabyte) storage space for a number of 1024 bits. The requirement is very hard to meet. The complexity class P which contains all decision problems that can be solved by a deterministic Turing machine using a polynomial amount of computation time, is generally believed to be ``easy". We point out that the time is estimated only in terms of the amount of arithmetic operations. It does not comprise the time for reading and writing data on the tape in a Turing machine. The flaw makes some deterministic polynomial time algorithms impractical, and humbles the importance of P=NP question.

Full-Text

Contact Us

service@oalib.com

QQ:3279437679

WhatsApp +8615387084133