Average Complexity

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

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.