拉马莫汉·帕图里是理论计算机科学家,加州大学圣迭戈分校计算机科学教授。他的研究集中于计算复杂性理论和可满足性问题的算法。
他与拉塞尔·因帕利亚佐共同提出了指数时间假设(ETH),并且是PPZ算法和PPSZ算法的合作者之一,这些算法能以快于2^n穷举搜索的速度求解k-SAT。
拉马莫汉·帕图里
加州大学圣迭戈分校计算机科学教授,以k-SAT算法和指数时间假设研究而闻名。
拉马莫汉·帕图里是理论计算机科学家,加州大学圣迭戈分校计算机科学教授。他的研究集中于计算复杂性理论和可满足性问题的算法。
他与拉塞尔·因帕利亚佐共同提出了指数时间假设(ETH),并且是PPZ算法和PPSZ算法的合作者之一,这些算法能以快于2^n穷举搜索的速度求解k-SAT。
本条目依据AIPOST的文章与广为人知的事实整理。如有错误,请通过更正请求告诉我们。
这一假设由Russell Impagliazzo、Ramamohan Paturi和Francis Zane在大约三十年前提出,断言求解该问题的k-CNF版本所需的时间会随变量数量严格呈指数增长。
阅读文章百科说明依据AIPOST的文章与广为人知的事实整理。如有错误,请通过更正请求告诉我们,我们会核实并修改。新文章中出现的名称会在文章发布后加入百科。