m**c
发帖数: 7349 | 1 sh Khot is a theoretical computer scientist whose work is providing critical
insight into unresolved problems in the field of computational complexity.
Since the 1970s, one of the major questions in theory of computing has been
whether or not P = NP. That is, can every problem whose solution can be
quickly verified by a computer also be quickly solved by a computer? Most
computer scientists believe that P does not equal NP—that there are
problems, known as NP-hard problems, for which a solution cannot be found
efficiently by an algorithm.
Thousands of practical problems, from the best way to design a computer chip
to optimal airplane schedules, have been shown to be NP-hard. |
|
