Ссылка на работы [22] и [23] освобождает меня от необходимости описывать историю становления и развития в TCS (эту аббревиатуру я принимаю как более предпочтительную, чем информатика) соотношения между классами задач P и NP. В этих работах с достаточной полнотой обрисовано прошлое и настоящее этой проблематики, а вот будущее осталось неопределенным, поскольку автору указанных работ не было известно: NP = P или NP =/= P.
Теперь, когда стало известно, что NP = P, следует предупредить всех, кто имеет дело с современной криптографией с открытым ключом, что все ее выводы (см., например, [24]) о временных потребностях взломщика, основаны на предположении: NP =/= P. Но это предположение не верно. Такие задачи, как умение разлагать большие числа на множители, брать дискретный логарифм в конечном поле и многие другие, которые входят в перечень NP-полных задач, могут решаться алгоритмами с полиномиальной временной сложностью, поэтому, ставки, которые делались раньше и могли считаться достаточно обоснованными, теперь становятся очень зыбкими, если не сказать даже смешными, но с вполне возможными печальными последствиями.
Так как распознавание ВЫП является частным случаем суперприведения задачи ВЫП, то дальнейшее в п. 5.