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.