|
|
Logic & Semantics |
|
|
Logic & Semantics |
One way to cope with the phenomenon of NP completeness is to try to solve the problem quickly on average with respect to the relevant distribution on instances. That works in many cases, but some randomized NP problems remain hard even on average. We explain, motivate and justify basic definitions of the average-case completeness theory, and sketch the current state of affairs. In addition (time permitting), we will argue that the famous P=?NP question isn't the best question to concentrate upon and will suggest an alternative.
