Проблема на миллион долларов. "P=NP или P≠NP"

Существует такая известная математическая проблема "P=NP?", за решение которой Математический институт Клэя в 2000 году назначил премию в миллион долларов США.

Всего существует 7 задач, за которые объявлен столь большой приз. На данный момент только одна из семи проблем (гипотеза Пуанкаре) решена Григорием Перельманом, который отказался от приза в миллион долларов, а также от получения Филдсовской премии, которая вручается один раз в 4 года молодым математикам не старше 40 лет.

Проблема P=NP (или P≠NP) известна с 1971 года, но до сих пор считается неразрешенной. Разумеется, постоянно предпринимаются попытки решить эту задачу. Может, кто-то за миллионом гонится, а может ради науки.

Всего существует три возможных ответа на вопрос проблемы. 1) "P=NP", 2) "P≠NP", 3) невозможно доказать, "P=NP или P≠NP". Мне, конечно, видится, что есть еще четвёртый вариант, который состоит в том, что верен третий вариант, но невозможно доказать, что третий вариант верен, то есть что "P=NP?" доказать невозможно, но мы в эти дебри лезть не будем.

Австрийский математик Gerhard J. Woeginger создал в интернете страничку (https://www.win.tue.nl/~gwoegi/P-versus-NP.htm), куда собирает "доказательства" для проблемы P=NP в хронологическом порядке. Таких доказательств уже 107 штук и датированы они начиная с 1986 года по 2015.

Каждое "доказательство" имеет одну из трех пометок "Equal", "Not equal", "Unprovable", что соответствует трем описанным выше случаям. Четвертый случай по понятным причинам не мог бы возникнуть в этом списке. Кроме того, там написана краткая идея каждого из 107 доказательств.

Например, в марте 2014 года Joonmo Kim доказал, что P≠NP. Доказательство использует искусственно разработанную машину Тьюринга, которая генерирует экземпляры задачи выполнимости, и проверяет их выполнимость. А в сентябре 2014 года Анатолий Панюков доказал P = NP путем построения алгоритма решения задачи о Гамильтоновом пути в графе за полиномиальное время. В его статье так и указано прям, за .

Так как все 107 доказательств не могут быть верны одновременно, то примерно половина из них гарантированно содержит ошибки: либо те, что утверждают, что P=NP, либо остальные. Ко многим доказательствам имеется ссылка на pdf-файл с научной статьей. Каждый желающий может поискать ошибки и, возможно, исправить.

Думаю, что скоро новые доказательства появятся. Миллион все еще ждет своего гения.

По поводу траура

Сегодня, во всей стране объявлен траур из-за авиакатастрофы. И в сети стали появляться обвинения в сторону тех, кто несмотря на это продолжил жить обычной жизнью. Так, например, патриарх Кирилл был поражен, что некоторые люди решили отметить ему малопонятный праздник Хэллоуин. Выскажусь и я.

Каждый день у каждого человека происходят какие-нибудь события в жизни. Но у всех эти события разные. У одних сегодня свадьба, у других похороны, в третьей семье кто-то очень болен, в четвёртой сын родился, в пятой день рождения, в шестой отец обещал сыну в цирк сходить и давно купил долгожданные билеты. Все испытывают разные эмоции. Ежедневно умирают люди в автокатастрофах. Должны ли мы отменить все свадьбы из-за этого? Или, напротив, те, у кого похороны, должны ли они отмечать с соседями Новый год или пасху? Может, папа должен выбросить билеты в цирк и отменить обещание сводить туда сынишку, у которого день рождения и он этого так долго ждал? Разумеется, нет. Все люди испытывают разные эмоции. У каждого своя персональная жизнь. Они радуются, когда им весело и тоскуют, когда у них не очень хорошо. Выравнять всех под одну гребенку и заставить страдать одинаково и в один и тот же день — глупость.

Мне очень жаль всех погибших. Я не хотел бы оказаться ни на их месте, ни тем паче на месте их родственников. Но я не просил весь мир со мной переживать, когда у меня в семье случалась беда. И я прошу весь мир меня понять, что я не буду вместе с ними переживать по их несчастью. Иначе моя жизнь превратиться в постоянный траур. Дайте мне возможность самому испытывать те чувства, которые у меня есть! Хочу радоваться и веселиться, когда у меня хорошо.

P.S. Позвоню-ка я бабушке и поздравлю её с днем рождения. Она очень ждет.

Качество службы

Как выяснить, качественно ли проведен церковный обряд? Ну вот если мне сделали плохую прическу или фальшиво спели на концерте, за который я заплатил, то понятен критерий. А как проверить качество службы? Есть какие-то эксперты, которые понимают, что тот или иной поп никудышно молится, недостаточно поклонов делает или не так кадилом машет?

Святейший титул

Меня всегда веселит скромность попов. Все эти титулы, которые они сами себе выдумывают: "владыка", "святой отец". А "Святейший" — не, ну посмотрите какая наглость. Как в детском фильме про кащея: "самый могучий, самый наилучший, ничего не скажешь — молодец." Вообщем, наимудрейший из наимудрейших. Впрочем, от них не далеко ушли казаки, которые любят себе грудь, как новогоднюю елку, самопридуманными медалями украшать, да всякие великие князья и княгини с их императорскими орденами. Сумасшедшие, что сказать! И все таки попы по тщеславию, хвастовству и стяжательству переплюнули всех.

(фотка с просторов интернета)

Шрифты

Для того, чтобы написать хорошую книгу, статью или заявление на отпуск, нужны хорошие шрифты. Конечно же, нужен не один шрифт, а несколько. Обычно для книги или статьи вам может потребоваться до 10 разных шрифтов. В любой программе, которые позовляют создавать текстовые документы есть шрифты по умолчанию. Если программа хорошая, то эти шрифты выглядят удачно. Но люди постоянно гонятся за какими-то новыми шрифтами. Повсюду коллекции: 1000 таких то шрифтов, 10000 таких то, рукописные, жирные, моноширинные. Большинство из них следует выбросить в помойку (или в корзину на рабочем столе). Очень много уродливых. Тем не менее многие пользователи уверены, что если они в своей статье будут использовать особые буквы, например с завитушками, то их текст будет выглядеть намного красивее. Причем новички выбирают примерно одни и те же шрифты по делу и не по делу, такие как Arbat, Jacob или Trixie, например, которые опытный пользователь за километр видит. Часть шрифтов вообще годится лишь для заголовков, но кто-то умудряется писать ими обычный текст.

На мой взгляд использовать шрифты, отличные от тех, что предоставлены по умолчанию, можно лишь в особых случаях:
1) вам нужны особые символы, например, для Ваших математических формул;
2) вы хотите создать книгу, оформленную уникально, чтобы ни у кого так не было, тогда вам надо создать собственный набор шрифтов;
3) вы профессиональный дизайнер (без комментариев).

Я готовлю текстовые документы с помощью системы TeX. Многие делают это в таких программах как Microsoft Word или Open Office Writer. Для написания хорошей статьи или книги обычно требуются следующие виды шрифтов. Все примеры рисунков со шрифтами взяты из системы TeX.

1) Шрифт с засечками. Шрифт для написания обычного текста в документе. В любой хорошей книге традиционно гарнитура устроена так, что буквы имеют дополнительные засечки. В Windows роль такого шрифта может выполнять Times. А для системы TeX Дональд Кнут разработал семейство шрифтов Computer Modern, среди который есть и шрифт с засечками cmr. Русская версия шрифтов Computer Modern (LH-шрифты) была написана Ольгой Лапко. Шрифт с засечками для Windows-кодировки носит название larm. Шрифты Computer Modern и LH-шрифты распространяются свободно.



2) Шрифт без засечек. Такой шрифт нужен, чтобы делать заголовки или подписи к рисункам. Иногда им пишут сноски, цитаты или выделяют важные абзацы. Газеты обычно печатаются шрифтами без засечек. Но книга, полностью написанная такой гарнитурой выглядит некрасиво. В Windows с ролью шрифта без засечек хорошо справляется Arial. Обидно только, что в Word он установлен по-умолчанию, поэтому документы неопытных пользователй почти все написаны шрифтом Arial, что выглядит ужасно.



3) Полужирный шрифт. Шрифт для выделения некоторых важных понятий в тексте. Совершенно неприемлемо, если этим шрифтом будут писаться целые абзацы. В этом случае огромные части страницы будут более плотно залиты краской, что выглядит очень плохо.




4) Курсивный шрифт. Еще один альтернативный способ выделения слов в тексте. Если вы хотите ухудшить читаемость текста, пишите им полностью предложения, абазацы, да и всю книгу, впрочем (шутка). Кстати, мне совершенно не нравятся буквы x, i, j, t в italic версии шрифта Times. Насколько симпатичнее выглядят аналогичные из семейства Computer Modern:



5) Наклонный шрифт. Шрифт для повышения акцента на чем-то важном. Как же мне нравится этот шрифт! Он не так выделяется, как курсивный, поэтому легче читается, но слегка придает вашей идее оттенок важности. К сожалению, в Windows аналога я не знаю.




6) Моноширинный шрифт. Шрифт для написания компьютерных текстов. Программисты любят писать свои алгоритмы шрифтом, в котором все буквы имеют одинаковую ширину. В Windows обычно это шрифт Сourier, хотя лично мне он не нравится. В TeX такой шрифт напоминает печатную машинку.



7) Математические шрифты. Иногда хочется написаь какую-нибудь формулу:



8) Капитель. Интересный способ выделения слов. Все буквы имеют начертания, как у прописных, но если буква должны быть строчной, то она просто меньше по размеру.



9) Экзотические шрифты типа полужирного курсива. Такое двойное выделение я обычно не использую и другим не советую.






В целом, я не могу понять, чем могут не устраивают шрифты LH, сделанные Ольгой Лапко для TeX или шрифты Times, Arial, Courier для Open Office? Зачем использовать шрифты c другим рисунком букв? Чего в них особенного? Какое-то важное новое начертание? Есть какой-то особый курсив? Они красивее?

Я понимаю, если нужен шрифт для ваших формул. Также понимаю идею создать свою отличную от других работу шрифтом, которого ни у кого нет и нужен уникальный шрифт (как создал Д.Э.Кнут для своей книги "Конкретная математика"), но тогда надо его заново самому разрабатывать. А искать шрифт, лишь чуть отличающийся от LH, зачем? Там те же буквы с засечками, без засечек, наклонные, курсивные,
полужирные и моноширинные.

Я ошибаюсь? С уважением, Алексей Малистов.

50% плюс 1 голос или полтора землекопа

1) «Чтобы одержать победу на выборах мэра в первом туре, необходимо набрать 50% плюс 1 голос.»
2) «Контрольный пакет состоит из 50% и 1 акции.»

Доколе это будет продолжаться? Кто придумал эту фразу про «50% плюс один»?

Если на выборах проголосовало нечетное количество человек (вероятность этого события для большого города, кстати, равна 50/50), то 50% плюс 1 непременно окажется дробным числом.

Допустим, что члены кооператива в составе 23 человек выбирают председателя. Так вот, 50% плюс 1 человек это 12,5 (двенадцать с половиной) человек. Мало того, что такого числа голосов не набрать, если только один из присутсвующих не страдает раздвоением личности, но важно, что достаточно для принятия решения 12 человек (или 50% плюс полголоса).

Чтобы не получилось как у Лии Гераскиной «В стране невыученных уроков» с землекопами, нужно формулировать фразу верно:
1) «Чтобы одержать победу на выборах мэра в первом туре, необходимо набрать более 50% голосов.»
2) «Контрольный пакет должен содержать более 50% акций.»

Ведь есть такое точное и понятное слово более. Зачем выдумывать бред про «50% плюс один» и плодить половинки землекопов?

Больничный по совместительству

Я работаю в двух местах, условно называемых законом «основная работа» и «работа по совместительству». Недавно я заболел и мне пришлось лечиться дома, периодически заходя к врачу в поликлинику. Разумеется, по окончании моего лечения, мне врач выдал больничный, который был заверен печатью в регистратуре.

В больничном листе проставляется место работы, дата начала амбулаторного лечения и дата выписки, а также разные подписи и печати. Из-за того, что место работы в больничном фиксируется, я решил обратиться в регистратуру за получением второго экземпляра на вторую работу, которая по совместительству. Но не тут то было! Мне заявили, что задним числом мне выписывать второй больничный не будут.

Я не понимаю! Факт моей болезни установлен, зафиксирован в документах клиники, заверен в регистратуре, подписан врачом. Больничный мой абсолютен по своей сути, он имеет начало и конец и даже диагноз. Не зависимо ни от какой работы, да и ни от кого бы то ни было вокруг, то есть где бы я не трудился, факт наличие у меня болезни в указанный период не может измениться. Я болел и это доказано! Какого хрена мне не дают больничный на вторую работу?

Я считаю, что больничный лист не должен содержать ни каких данных о работе. В нем лишь должна быть установлена степень моей болезни и сроки. Этот больничный должен дублироваться по моему желанию в любое рабочее для поликлиники время. При этом я хочу иметь возможность получить его хоть через 16 лет, если он мне потребуется для доказательства моей болезни. А с вопросами разных компенсаций по болезни должна разбираться бухгалтерия на работе, для которой я принесу одну из копий больничного. Пусть у нее еще будут хоть двадцать дополнительных листов, в которых они будут указывать данные для налоговой и других служб, те данные, которые сейчас рисуются на оборотной стороне больничного листа.