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

[avva]

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

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