Average Complexity

平均复杂度

• 批准号: 9820611
• 负责人: Jie Wang
• 金额: $ 11.24万
• 依托单位: University of North Carolina Greensboro
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 1999
• 资助国家: 美国
• 起止时间: 1999-09-01 至 2001-11-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9820611&HistoricalAwards=false
• 关键词: Average; Complexity

CCR-9820611WangThis research is directed towards a further understanding of average complexity of NP-complete problems. NP-complete problems are generally thought of as being computationally intractable. But NP-completeness is a worst-case concept; some NP-complete problems are easy on average, though some may not be. Levin introduced the notion of NP-completeness and used it to distinguish intrinsically hard-on-average problems. A small number of problems have since been shown to be NP-complete on average, but this situation is far from satisfactory. Finding new average complete problems remains a main issue in average complexity theory. The project is aimed at a systematic investigation of the average complexity of concrete problems. The goal here is to obtain a new list of average NP-complete problems and develop new techniques for proving average completeness results.

本研究旨在进一步理解NP完全问题的平均复杂性。 NP完全问题通常被认为是计算上难以处理的。 但NP完全性是一个最坏情况的概念;有些NP完全问题平均来说很容易，尽管有些可能不容易。 莱文引入了NP完全性的概念，并用它来区分本质上难以平均的问题。 有少数问题被证明是平均NP完全的，但这种情况远远不能令人满意。 寻找新的平均完全问题一直是平均复杂性理论的一个主要问题。 该项目旨在对具体问题的平均复杂性进行系统调查。 这里的目标是获得平均NP完全问题的新列表，并开发用于证明平均完整性结果的新技术。