Average Complexity

CCR-9820611Wang本研究旨在进一步理解NP-完全问题的平均复杂性。NP完全问题通常被认为在计算上是难以处理的。但NP-完备性是一个最坏的概念；一些NP-完全问题平均来说是容易的，尽管有些可能不是。Levin引入了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.