Аннотация:The P vs NP problem arose from the question of whether exhaustive search is necessary for problems with short verifiable solutions. We still do not know if even a slight algorithmic improvement over exhaustive search is universally possible for all NP problems, and to date no major consequences have been derived from the assumption that an improvement exists.
