Russell Impagliazzo

拉塞尔·因帕利亚佐

美国理论计算机科学家,任教于加州大学圣迭戈分校,以提出指数时间假设和复杂性“五个世界”分类而闻名。

1篇文章最近提及

拉塞尔·因帕利亚佐是美国理论计算机科学家,加州大学圣迭戈分校计算机科学教授。他在加州大学伯克利分校师从曼纽尔·布卢姆获得博士学位,研究领域包括计算复杂性理论、密码学和伪随机性。

他与拉马莫汉·帕图里在研究k-SAT复杂性时共同提出了指数时间假设(ETH)。1995年,他提出了被广泛引用的“五个世界”框架,根据P与NP问题和密码学的关系将可能的世界分为Algorithmica、Heuristica、Pessiland、Minicrypt和Cryptomania。关于伪随机生成器与去随机化的因帕利亚佐–威格德森定理也以他的名字命名。

本条目依据AIPOST的文章与广为人知的事实整理。如有错误,请通过更正请求告诉我们。

涉及该条目的文章

  • OpenAI模型推翻指数时间假设,但P≠NP仍未动摇AI资讯 ·

    这一假设由Russell Impagliazzo、Ramamohan Paturi和Francis Zane在大约三十年前提出,断言求解该问题的k-CNF版本所需的时间会随变量数量严格呈指数增长。

    阅读文章

发现说明有误或找不到条目?

百科说明依据AIPOST的文章与广为人知的事实整理。如有错误,请通过更正请求告诉我们,我们会核实并修改。新文章中出现的名称会在文章发布后加入百科。