Немножко про работу

[darnley]

Немножко про работу. Пара шуток для посвящённых.

В одном маленьком, но полезном экселевском файлике живёт табличка, в которой записана вычислительная сложность нескольких маленьких, но полезных задач.

В течение последнего времени в некоторых графах этой таблички было чёрным по-белому написано: NPC, то есть NP-полные.

После одного разговора с kgeorgiy во

Comments

[allocco]

Ты ещё на какую-нибудь теоретико-числовую книжку посмотри. Там таких лемм --- хоть методом Виноградова ешь :)

[darnley]

Ну там они, может, хоть естественным образом берутся. А как может при покрытии графа двудольными подграфами сам по себе всплыть интервал 8981..8989?

Впрочем, я выяснил ответ: это число 8985 из теоремы Ramsey плюс-минус четыре. Ну так и назовите это RN±ε, где RN - Ramsey Number, а ε - что-то маленькое. И где-нибудь упомяните что ε=4 подходит. Зачем терзать читателя техническими подробностями, не имеющими сакрального смысла? Почему глупые программисты это понимают, а умные математики - нет?

[allocco]

Как раз там все такие числа берутся от оценок, до которых смогли дойти; а вот число Рамсея выглядит здесь куда более естественно. Так что "дурацкие числа" в т.ч. --- маркеры того, до куда простирается техническая мысль при доказательстве, а число Рамсея здесь --- маркер идеи доказательства :)

[darnley]

Я не спорю, всё так. Но почему я, читая статью, должен держать в голове и при каждой встрече узнавать конкретное число 8985?! Я вот этого не понимаю. Я лучше запомню пинкод от своей банковской карточки! А это число уберите от меня подальше, как и фотографии того, как делают еду, которую я ем в «Чайной ложке» и прочих «Всяких штучках». Не хочу я знать технические подробности, извольте прикрыться, господа.