среда, 20 ноября 2013 г.

Folding@home

"Help Stanford University scientists studying Alzheimer's, Huntington's, Parkinson's, and many cancers by simply running a piece of software on your computer.

The problems we are trying to solve require so many calculations, we ask people to donate their unused computer power to crunch some of the numbers."

http://folding.stanford.edu

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

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

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

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

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

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