多项式时间(世界上最难的三道题)

多项式时间，世界上最难的三道题？

1.费马猜想

多项式时间(世界上最难的三道题)

又称“费马大定理”或“费马问题”，1637年由法国数学家费马提出，若用不定方程来表示，费马大定理即当整数n>2时，关于x,y,z的方程x+y=z没有正整数解。用数学语言来表达就是：形如x n＋y n＝z n的方程，当n大于2时没有正整数解。剑桥大学怀尔斯在1995年彻底解决了这一大难题。

2.四色猜想

世界近代三大数学难题之一，四色猜想的提出来自英国。1852年，毕业于伦敦大学的弗南西斯·格思里，来到一家科研单位搞地图着色工作时，发现了一种有趣的现象：“看来，每幅地图都可以用四种颜色着色，使得有共同边界的国家着上不同的颜色。”这个结论能不能从数学上加以严格证明呢?他和在大学读书的弟弟格里斯决心试一试。兄弟二人为证明这一问题而使用的稿纸已经堆了一大叠，可是研究工作没有进展。1976年，美国数学家阿佩尔与哈肯在美国伊利诺斯大学的两台不同的电子计算机上，用了1200个小时，做了100亿次判断，终于完成了四色猜想的证明。

3.哥德巴赫猜想

世界近代三大数学难题之一。1742年6月7日，哥德巴赫写信给当时的大数学家欧拉，提出了以下想法：任何一个大于等于6的偶数，都可以表示成两个奇质数之和；任何一个大于等于9的奇数，都可以表示成三个奇质数之和。这就是著名的哥德巴赫猜想。至今仍没人能证明，最接近成功的是陈景润。

哥德巴赫是德国一位中学教师，也是一位著名的数学家，生于1690年，1725年当选为俄国彼得堡科学院院士。1742年，哥德巴赫在教学中发现，每个不小于6的偶数都是两个素数(只能被和它本身整除的数)之和，如6＝3＋3, 12＝5＋7等等。

克拉默法则通俗易懂？

1、克拉默法则通俗解释：克拉默法则是线性代数中一个关于求解线性方程组的定理。它适用于变量和方程数目相等的线性方程组。

2、克莱姆法则，又译克拉默法则（Cramers Rule）是瑞士数学家克莱姆（1704-1752）于1750年，在他的《线性代数分析导言》中发表的。其实莱布尼兹〔1693〕，以及马克劳林〔1748〕亦知道这个法则，但他们的记法不如克莱姆。

3、对于多于两个或三个方程的系统，克莱姆的规则在计算上非常低效；与具有多项式时间复杂度的消除方法相比，其渐近的复杂度为O（n·n！）。即使对于2×2系统，克拉默的规则在数值上也是不稳定的。

4、克莱姆（Cramer,Gabriel，瑞士数学家 1704-1752）克莱姆1704年7月31日生于日内瓦，早年在日内瓦读书，1724 年起在日内瓦加尔文学院任教，1734年成为几何学教授，1750年任哲学教授。他自 1727年进行为期两年的旅行访学。在巴塞尔与约翰．伯努利、欧拉等人学习交流，结为挚友。后又到英国、荷兰、法国等地拜见许多数学名家，回国后在与他们的长期通信中，加强了数学家之间的联系，为数学宝库也留下大量有价值的文献。他一生未婚，专心治学，平易近人且德高望重，先后当选为伦敦皇家学会、柏林研究院和法国、意大利等学会的成员。

dlog？

1 dlog-m 是求离散对数的算法。2 离散对数是指在一个与模数相关的群中，一个数a的k次方能得到一个特定数b，那么k就是a对于模数的离散对数。dlog-m算法就是用来求离散对数的一种算法。3 dlog-m可以在多项式时间内求离散对数，它在密码学中有很重要的作用，被广泛用于设计和破解密码算法。

什么叫多项式时间算法？

定义：若存在一个常数C，使得对于所有n>=0，都有|f(n)| <= C*|g(n)|，则称函数f(n)是O(g(n))。时间复杂度是O(p(n))的算法称为多项式时间算法，这里p(n)是关于n的多项式。不能够这样限制时间复杂度的算法被称为指数时间算法。例如：时间复杂度为O(nlog(n))、O(n^3)的算法都是多项式时间算法，时间复杂度为O(n^log(n))、O(n!)、O(2^n)的算法是指时间算法。一个优化问题如果已经找到了多项式时间算法，则称该问题为多项式时间可解问题，并将这类问题的集合记为P，因此多项式时间可解问题就称为P类问题。一个问题如果没有找到多项式时间算法，那么直觉上它是“难解”的，但又往往无法证明多项式时间算法的不存在性。由于在寻找有效算法上的失败未必一定意味着这样的算法不存在，这就给理论工作者带来了一个难题：一方面证明一个问题不存在多项式时间算法是困难的，至今尚未给出；另一方面有越来越多的问题无法给出多项式时间算法。同时，理论工作者又渴望解决此难题。为此，在20世纪70年代提供了一个漂亮的理论，它把这种失败归结为一个深刻的数据猜想，这个理论就是NP-完全性理论。定义：给定一个判定问题，如果存在一个算法，对任何一个答案为“是”的实例I。该算法首先给出一个猜想，该猜想规模不超过I的输入长度的某个多项式函数，且验证猜想的正确性仅需多项式时间，则称该问题属于NP类。定义：如果NP类中所有问题都可以多项式时间归约到NP类中某个问题x，则称x是NP-完全问题。定义：如果某优化问题x的判定问题是NP-完全的，则称问题x是NP-难的；如果x的判定问题是强NP-完全的，则称x是强NP-难的。