October 4th, 2005

moose, transparent

компьютерное, или лошадиная фамилия

Вот аналогия. Предположим, вы пытаетесь вспомнить какую-то фамилию, какого-то человека. Но никак не вспоминается. Вот уже почти совсем, но никак. Но вы знаете, чувствуете, что если вдруг её увидите где-то, или кто-то вам скажет, то вы поймёте, что это она. Это — NP-проблема. Тогда знаменитую нерешённую проблему P?=NP можно сформулировать так: если чувствуешь, что узнаешь, когда тебе скажут, но сам вспомнить не можешь, то на самом деле есть способ и самому вспомнить (причём относительно быстро, не перебирая весь телефонный справочник). Какой это может быть способ, правда — никто не знает, и большинство учёных склоняется к тому, что его и вовсе нет.

А NP-полная проблема в этой аналогии соответствует такому Главному Имени, что если его научишься вспоминать — то все остальные будет уже легко вспомнить...
moose, transparent

перекличка цитат

"Omne ignotum pro magnifico" — "Всё неизвестное кажется грандиозным". Тацит.

"Any sufficiently advanced technology is indistinguishable from magic" — "Любая достаточно развитая технология неотличима от магии". Артур Кларк.

[заметил Таль]
moose, transparent

американская политика

Насколько хорошим был первый бушевский выбор кандидата в Верховный суд (Робертс), настолько плохим и диким оказался второй (Майерс). Даже крайне правые и консерваторы взбунтовались.

Любопытно будет, если найдётся достаточно республиканцев в сенате, готовых её прокатить.