понедельник, 21 января 2013 г.

Аббревиатура на все случаи жизни

В одной из последних лекций на образовательном ресурсе Coursera проф. Тим Рафгарден поведал о любопытном факте. Когда математики и программисты второй половины XX века думали о том, как назвать те задачи, которые мы привыкли именовать NP-полными, среди прочих был предложен следующий вариант - английская аббревиатура PET. Вариант, как видим, не прижился, однако достоин упоминания вследствие лингвистической находчивости авторов.

В чем же эта находчивость проявляется?
Как известно, доказательство неравенства классов P и NP еще не получено, и поэтому нельзя аргументированно заявлять о том, что эти задачи можно решить только экспоненциально. Поэтому PET можно расшифровать как "probably exponential time".

Но прогресс не стоит на месте и когда-нибудь это доказательство может быть получено. Тогда аббревиатура останется прежней, поменяется лишь расшифровка - "provably exponential time". Теперь давайте представим что дед мороз существует и P = NP. И даже в этом случае аббревиатуру не пришлось бы менять - задачи стали бы называть "previously exponential time".

Привычный  нам термин NP-сomplete, впрочем, тоже не является уязвимым к разным разгадкам этой мировой загадки.

Комментариев нет:

Отправить комментарий