Калькулятор врет что делать
Простые способы проверить точность калькулятора
Людям свойственно ошибаться, признаваться в своих ошибках не любит никто. Поэтому человечество и придумало множество приспособлений и технических средств, чтобы минимизировать возможные ошибки, упростить и ускорить процесс принятия решений и точность выполнения разнообразных процессов и вычислений. Но теоретически умные электронные устройства и программы тоже могут ошибаться и работать не точно.
Поэтому стоит подстраховываться и заранее проверять точность вычислений выбранных устройств.
Попробуем это сделать на примере обычного калькулятора. Сегодня калькуляторы можно найти везде – в телефонах, часах, плеерах, других электронных устройства, кроме того калькулятор, как самостоятельное устройство тоже никто не отменял.
Общие сведения
Этот инструмент расчетов будет востребованным еще долгое время, вероятнее всего, чем дальше, тем более востребованным он будет становиться. Калькулятор нужен студентам и школьникам, менеджерам и бухгалтерам, домохозяйкам и инженерам.
Сегодня найти в продаже калькулятор довольно легко, кроме того, он чаще всего встроен в другие электронные устройства. А наши родители только мечтали о таком чуде техники, которая делает сложные вычисления за пару секунд. Жизнь студентов, школьников, домохозяек и инженеров стала легче только в 1970х года, когда появились в свободной продаже компактные калькуляторы (их компактность и эргономичность с современными уже никак не сравнить).
Калькуляторы бывают разных типов:
Любой калькулятор должен быть заключен в прочный корпус, иметь емкий аккумулятор, достаточное количество цифровых ячеек на дисплее. Сегодня вообще калькуляторы встраиваются в любое мобильное устройство от часов до компьютера. Так или иначе, внешний вид калькулятора, по сути, мало чем отличается от первых образов. Это дисплей, где отражаются вводные данные и результаты вычислений, и клавиатура, для введения этих самых данных. Все процессоры и микросхемы спрятаны внутри корпуса устройства. Главное в любом вычислительном устройстве – точность и надежность самих вычислений.
Простые способы проверить работоспособность и точность работы калькулятора
Перед использованием калькулятора или его покупкой стоит произвести простые вычислительные действия. Сделать это можно легко в любой момент, когда у вас появиться подобная потребность или возникнут сомнения в правильности выполненных расчетов. Никаких дополнительных инструментов и приспособлений не понадобиться – достаточно только самого калькулятора.
Простые способы
12345679*9 = 111111111
12345679*18 = 222222222
12345679*27 = 333333333
12345679*36 = 444444444
12345679*45 = 555555555
12345679*54 = 666666666
12345679*63 = 777777777
12345679*72 = 888888888
12345679*81 = 999999999
Серьезные способы проверки работы калькулятора
Бывают ситуации, когда нужна абсолютная уверенность в точности работы вычислительного устройства, например, при расчете в научных или технических процессов. Тут будет крайне важна точность, а не приблизительность вычислений. Как показывает практика, вычисления на простых бытовых калькуляторах могут выдавать довольно существенные погрешности в десятки, а иногда и сотни раз. Для определения точности расчетов вычислительного устройства использует более сложная формула. Вводить ее важно не частями, а сразу целым массивом данных.
Если полученный ответ приблизительно будет равен «-1», то можно смело доверять вашему калькулятору самые сложные расчеты, и не беспокоиться за точность вычислений.
Стоит отметить, что с таким вычислением не справляется большинство самых современных калькуляторов. Если вам точность очень важна, а калькулятор отказывается вам в этом помогать, то можно воспользоваться современными компьютерными программами, которые имитируют вычислительные процессы и гарантируют точность результатов.
Что еще важно при выборе калькулятора?
Информация на клавишах так же должна быть нанесена качественно – четко и разборчиво, кроме того краска должна быть стойкой к стиранию при длительном использовании, а шрифт достаточно крупным и читаемым, кнопки должны располагаться в удобных и привычных местах, нажиматься легко и плавно. Иначе вы рискуете постоянно сбиваться при вводе данных, что приведет к процессу затягивания вычислений.
Как правило, качественное устройство имеет хорошую фирменную упаковку и инструкцию по эксплуатации. Кстати, в самой инструкции производители довольно часто указывают способы проверки точности калькулятора. При покупке стоит обратить внимание и на сроки гарантии, чтобы при обнаружении неисправности обменять калькулятор на более качественный или вернуть свои деньги.
Подсчитаем баги в калькуляторе Windows
Введение
Калькулятор Windows наверняка знаком каждому пользователю этой операционной системы и не требует особого представления. Теперь же любой пользователь может изучить исходный код калькулятора на GitHub и предложить свои улучшения.
Общественность, например, уже обратила внимание на такую функцию:
которая логирует текст из буфера обмена и, возможно, отправляет его на серверы Microsoft. Но эта заметка не об этом. Хотя подозрительных примеров кода будет много.
Мы проверили исходный код калькулятора с помощью статического анализатора PVS-Studio. Так как код написан на нестандартном C++, многие постоянные читатели блога анализатора усомнились в возможности анализа, но это оказалось возможным. C++/CLI и C++/CX поддерживаются анализатором. Некоторые диагностики выдали ложные предупреждения из-за этого, но ничего критичного не произошло, что помешало бы воспользоваться этим инструментом.
Возможно, вы пропустили новости и о других возможностях PVS-Studio, поэтому хочу напомнить, что кроме проектов на языках C и C++, можно проанализировать код и на языках C# и Java.
Про неправильное сравнение строк
V547 Expression ‘m_resolvedName == L«en-US»’ is always false. To compare strings you should use wcscmp() function. Calculator LocalizationSettings.h 180
Я просматриваю отчёты анализатора, сортируя их по возрастанию номеров диагностик, и предупреждение на этот код было самым первым в списке, и очень удачным.
Дело в том, что здесь неправильно сравниваются строки. Получилось сравнение указателей вместо значений строк. Сравнивается адрес массива символов с адресом строкового литерала. Указатели всегда неравны, поэтому условие всегда ложно. Для правильного сравнения строк следует использовать, например, функцию wcscmp.
Кстати, пока я пишу эту статью, в заголовочном файле массив символов m_resolvedName превратился в полноценную строку типа std::wstring. И теперь сравнение работает правильно. К моменту, когда вы будете читать эту статью, скорее всего, многие другие ошибки тоже будут исправлены благодаря энтузиастам и таким исследованиям, как это.
Утечка памяти в нативном коде
V773 The function was exited without releasing the ‘temp’ pointer. A memory leak is possible. CalcViewModel StandardCalculatorViewModel.cpp 529
Мы видим указатель temp, ссылающийся на массив из 100 элементов, под который выделена динамическая память. К сожалению, память освобождается всего в одном месте функции, во всех остальных местах возникает утечка памяти. Она не очень большая, но это всё равно ошибка для C++ кода.
Неуловимое исключение
V702 Classes should always be derived from std::exception (and alike) as ‘public’ (no keyword was specified, so compiler defaults it to ‘private’). CalcManager CalcException.h 4
Анализатор обнаружил класс, унаследованный от класса std::exception через модификатор private (модификатор по умолчанию, если ничего не указано). Проблема такого кода заключается в том, что при попытке поймать общее исключение std::exception исключение типа CalcException будет пропущено. Такое поведение возникает потому, что приватное наследование исключает неявное преобразование типов.
Пропущенный день
V719 The switch statement does not cover all values of the ‘DateUnit’ enum: Day. CalcViewModel DateCalculator.cpp 279
Подозрительно, что в switch не рассмотрен случай с DateUnit::Day. Из-за этого в календарь (переменная m_calendar) не добавляется значение, связанное с днём, хотя метод AddDays у календаря присутствует.
Подозрительные сравнение вещественных чисел
Избыточность
Переменная op уже сравнивалась со значением NumbersAndOperatorsEnum::None и дублирующую проверку можно удалить.
Это гигантское условное выражение изначально имело ширину 218 символов, но я разбил его на несколько строк для демонстрации предупреждения. А переписать код можно до такого короткого и, главное, читабельного варианта:
V524 It is odd that the body of ‘ConvertBack’ function is fully equivalent to the body of ‘Convert’ function. Calculator BooleanNegationConverter.cpp 24
Анализатор обнаружил две функции, которые реализованы одинаково. По названиям функций Convert и ConvertBack можно предположить, что они должны выполнять разные действия, но разработчикам виднее.
Заключение
Наверное, каждый открытый проект от Microsoft давал нам возможность показать важность применения методологии статического анализа. Даже на таких маленьких проектах, как калькулятор. В таких крупных компаниях, как Microsoft, Google, Amazon и других, работает много талантливых программистов, но они такие же люди, которые делают ошибки в коде. Применение инструментов статического анализа кода — один из хороших способов повысить качество программ в любых командах разработчиков.
Проверь свой «Калькулятор», скачав PVS-Studio и попробовав на своём проекте. 🙂
Если хотите поделиться этой статьей с англоязычной аудиторией, то прошу использовать ссылку на перевод: Svyatoslav Razmyslov. Counting Bugs in Windows Calculator
Как проверить точность калькулятора?
Человеку свойственно ошибаться. Он не любит признаваться в этом публично, но прекрасно отдает себе отчет. Именно поэтому человечество создало множество технических приспособлений, задача которых – упростить, ускорить и гарантировать точность выполнения разнообразных востребованных процессов. Но что делать, если и машины начинают допускать ошибки? В теории это невозможно, ведь электронный «разум» не подвержен эмоциям, отвлекающим факторам и усталости. Но на практике нет-нет, да и закрадываются сомнения в достоверности полученных данных. Поэтому, принимая во внимание, что в электронике чудес не бывает, а бывают лишь плохие контакты, давайте попробуем подстраховаться и научиться проверять на точность хотя бы калькулятор.
Особенности устройства и работы калькулятора
Электронное вычислительное устройство, а проще говоря, калькулятор, прекрасно знакомо большинству современных школьников начиная с младших классов. Хотя еще их родители могли только мечтать о такой удобной «шпаргалке» и все арифметические операции выполняли в уме или «в столбик» на листе бумаги. Жизнь школяров и домохозяек, ведущих бухгалтерию семейного бюджета, стала легче в самом начале 1970-х годов, когда относительно компактные калькуляторы (их можно было удержать в одной руке) поступили в свободную продажу.
С тех пор появились специализированные инженерные («научные», поддерживают вычисление элементарных функций, числовые и символьные), бухгалтерские (с увеличенным числовым рядом и способностью автоматически вычислять прибыль, учитывать налоги конвертировать валюты), финансовые (могут рассчитывать суммы денежных потоков, дисконтов, выплат по кредитам в банковской сфере) и даже графические (выводят на дисплей рисунки и графики). Простейшие арифметические калькуляторы стали совсем миниатюрными и встраиваются в мобильные телефоны и наручные часы. Но типичная конструкция компактного электронного калькулятора осталась прежней по своей сути.
Наружу форм-факторов в разных вариантах выведены дисплей и клавиатура для ввода данных, а микросхемы памяти и процессора различной мощности спрятаны внутри. Они зашифровывают понятные и нужные людям числовые данные в виде машинного двоично-десятичного кода и используют их для арифметических вычислений. Как правило, эти математические задачи решаются по одному из трех путей логики операций. Это стандартные алгебраическая логика, арифметическая логика и так называемая логика вычислений с обратной польской записью. Но большинству пользователей достаточно знать, в какой последовательности вводить условия расчетов и как получить их итог.
К примеру, чтобы узнать, сколько будет «30*5+45» придется последовательно нажать кнопки клавиатуры: «3», «0», «×», «5», «+», «4», «5», а затем «=». По законам арифметики, после нажатия плюса выполнится умножение 30 на 5. В этот момент на дисплее отобразится промежуточный для примера результат «150», и только после нажатия на клавиатуре кнопки со знаком равенства отобразится окончательный результат вычислений: «195». А что касается достоверности этой информации, то тут остается поверить электронному «мозгу» или проверить исправность калькулятора, тем самым подтвердив или опровергнув точность его расчетов.
Для этого существует формула, которая «не по зубам» практически ни одному из ныне существующих калькуляторов. Зато с ее помощью вы сможете узнать, насколько ошибается именно ваша техника. Задайте калькулятору просчет результата по такой формуле, но вводите ее не по частям, а целым массивом:
Ответ, равный приблизительно минус единице, говорит о том, что вы можете смело доверять вашему калькулятору даже самые сложные расчеты, требующие высокой точности. Но будьте готовы к тому, что даже самый современный технический калькулятор покажет себя не лучшим образом в таком испытании. В этом случае можно посоветовать вам пользоваться так называемыми эмуляторами, или компьютерными программами, имитирующими электронную технику, но отличающимися от нее большим объемом памяти, сложностью вычислительных процессов и, соответственно, точностью результатов.
На что еще обратить внимание при выборе калькулятора
Проверку калькулятора на точность лучше всего осуществлять в самом начале его использования, непосредственно перед совершением покупки, чтобы сразу обезопасить свою работу от возможных ошибок. Заодно обратите внимание на другие характеристики устройства, влияющие на точность расчетов если и меньше процессора, то все равно заметно. Величина, разрешение и контрастность дисплея должны соответствовать сложности задач и вмещать достаточно количество символов, а также отображать их четко. Изображение на клавишах, качество его нанесения, стойкость к стиранию, а также сам размер и расположение кнопок должны быть удобными, практичными и интуитивно понятными. Иначе вы рискуете раз за разом сбиваться при вводе данных и начинать этот, порой кропотливый процесс, заново.
Качественная техника должна снабжаться фирменной упаковкой и обязательно сопровождаться инструкцией по эксплуатации устройства. Кстати, в этой инструкции добросовестные производители всегда указывают способ проверки точности калькулятора, один из тех арифметических, что мы рассмотрели выше. И, разумеется, уточните наличие и соблюдение гарантийных условий как со стороны производителя, так и продавца калькулятора. Потому что в случае обнаружения неисправности и регулярных ошибок расчетах вы должны иметь возможность вернуть неудачный прибор обратно. Желаем вам правильного выбора и точных вычислений.
Два калькулятора по-разному решают одно и то же уравнение
И дело тут не в более примитивной ошибке некоторых калькуляторов, которые не вычисляют умножение и деление прежде сложения и вычитания, а в том, следует ли вычислять так:
Баяны
183K постов 12.1K подписчика
Правила сообщества
Сообщество для постов, которые ранее были на Пикабу.
Поэтому я лучше лишние скобочки поставлю, чем выяснять, чего обкурились программисты, и откуда в простейшем выражении ошибки.
Потому что никто не читает мануалы. А ведь там написано, какие сокращения допускает нотация и как их раскрывать.
Неумение сформулировать задачу и попытка переложить ответственность на калькулятор не делает чести счетоводу. Научитесь корректно и однозначно записывать задачу и будет вам счастье.
1) надо читать инструкцию.
2) не давать машине думать за себя
3) использовать такой аппарат.
поэтому, чтобы не было путаницы, лучше выражение в таком виде записывать:
Ответ на пост «Забавная арифметика»
Что-то очень похожее я видел в книге Ричарда Фейнмана «Вы, конечно, шутите, мистер Фейнман!», в той главе, где он рассказывал о своём участии в оценке новых учебников по математике.
История проблемы равенства классов P и NP
В 2000 году Математический институт Клэя определил 7 математических задач, решение которых не могли найти в течение многих лет. За решение каждой из них была назначена награда в размере 1 миллиона долларов. Эти 7 задач известны как «задачи тысячелетия», и на сегодняшний день только одна из них была решена — гипотеза Пуанкаре. В этой статье пойдет речь о вопросе равенства классов P и NP, ответ на который может сильно повлиять на всю IT-сферу.
Равенство P и NP классов отсылает нас к теории алгоритмов, а именно к классам сложности. Первое, с чего стоит начать, это то, что классы P и NP классифицируют языки, а не задачи. Пока что это звучит довольно абсурдно, поэтому для понимания разберемся в некоторых деталях.
Пусть А — алфавит и L ⊆ А*, тогда L называется языком над А. Для любого алфавита пустое множество и А* являются тривиальными языками. При этом пустое множество часто называют пустым языком. Однако не стоит путать пустой язык и язык, содержащий пустое слово e, — они различны. Языки могут быть как бесконечными, так и нет, но обязательно счетными. Т. е. множество всех действительных чисел языком нельзя назвать, т. к. такой набор является неисчисляемым.
Говоря про абстрактный исполнитель, чаще всего имеют в виду машину Тьюринга, поэтому в дальнейшем под АИ будем подразумевать именно её. Итак, машина Тьюринга имеет неограниченное линейное хранилище, сгруппированное в ячейки. Каждая ячейка может содержать ровно один символ алфавита в любой момент времени. Вдоль ячеек идет считывающая головка, имеющая конечное число состояний. За одну итерацию она может считать значение только одной ячейки, переписать её значение, изменить свое состояние и перейти на одну позицию вправо/влево.
Устройство машины Тьюринга
На основе машины Тьюринга определим так называемую разрешающую машину над языком. Для начала введем определение характеризующей функции X(w). Функция X определяет, принадлежит ли слово w языку L. Если да, то значение функции равно «1»; если нет, то «0». Формально это можно записать так:
Разрешающей машиной D для языка L называется такая машина, которая для каждого w∈A вычисляет характеризующую функцию X(w) за конечное время.
В дополнение к разрешающей машине идет верификатор. Машина V, которая принимает слова w и c и выводит 0 или 1 после конечного числа шагов, называется верификатором для L, если она обладает следующими свойствами:
— выводит 1, только если w входит в язык L;
— для любого w в языке L существует такое c, что V(w,c) = 1.
Классы сложности и формулировка проблемы
Окей, мы рассмотрели несколько понятий. На первый взгляд, все это больше походит на лингвистику: алфавиты, слова, языки… Причем тут задачи? Чтобы ответить на этот вопрос, обратимся к понятию задача разрешимости (англ. Decision problem). Это такой вопрос (сформулированный в формальной системе), требующий ответа «да» или «нет», зависящего, возможно, от значений некоторых входных параметров. Например, «является ли данное натуральное число x простым?» или «даны два числа: x и y; делится ли x на y?« Метод решения в виде алгоритма называется разрешающей процедурой. Теория вычислимости имеет дело в основном с задачами разрешимости и приведенные выше конструкции наглядно соотносятся с таким типом задач: так разрешающая машина над языком является формализацией разрешающей процедуры. Но как же быть с задачами, такими как задача коммивояжера? На них нельзя дать бинарный ответ. В таких случаях применяют приемы приведения к версии decision problem. В случае коммивояжера проблема по-новому формулируется так: «существует ли маршрут не длиннее, чем заданное значение k?»
В класс сложности NP входят все языки L, для которых существует такой верификатор, что для каждого (w,c) время его работы полиномиально. Иными словами, NP включает в себя задачи разрешимости, для которых при подходящем сертификате для данного w мы быстро сможем удостовериться в том, что w действительно принадлежит L (ответ на вопрос можно довольно быстро проверить). Отсюда и название «верификатор». В качестве примера задачи в NP можно привести определение наличия в графе гамильтонова цикла. Сертификат в данном случае — последовательность вершин, образующих гамильтонов цикл.
Помимо этих классов можно выделить ещё 2: NP-hard и NP-Complete. Они основываются на приводимости одного языка к другому за полиномиальное время: пусть языки A и B — языки над одним алфавитом. Язык А будет приводимым за полиномиальное время к языку B, если существует такая функция f(w), что
— функция f может быть вычислена машиной Тьюринга за полиномиальное время.
Тогда в класс NP-hard будут входить языки, к которым приводимы все языки в NP (причем NP-hard язык может входить в NP, а может и нет), а в NP-Complete те языки, которые являются одновременно NP-hard и NP. Примером NP-Complete является язык выполнимых булевых формул (SAT). Таким образом, NP-Complete задачи образуют в некотором смысле подмножество «типовых» задач в классе NP: если для какой-то из них найден «полиномиально быстрый» алгоритм решения, то и любая другая задача из класса NP может быть решена так же «быстро».
Отношение между классами при равенстве и неравенстве
Теперь, немного погрузившись в теорию алгоритмов, более конкретно обозначим проблему равенства данных классов. Итак, множество P входит в множество NP, но неизвестно, существуют ли языки, которые входят в NP и не входят в P. Что это означает на практике? Итак, простыми словами класс NP можно охарактеризовать как «трудно решить, легко проверить». Классическим примером задачи, входящей в NP, является задача коммивояжера, для решения которой на данный момент известен лишь один алгоритм — старый добрый перебор (мы не рассматриваем эвристические методы). Однако, получив ответ, его будет не так сложно проверить. Класс P же вобрал в себя те задачи, для которых существует эффективный алгоритм решения, позволяющий решать их за полиномиальное время. И равенство или, наоборот, неравенство этих классов пока не доказано. Если эти классы равны, то это будет значить, что для всех задач, которые сейчас решаются путем перебора или другим неэффективным методом, существует(-ют) полиномиальные алгоритмы. А если не равны, то придется смириться с неоптимальностью решения этих задач.
История проблемы равенства P и NP началась в 1928 году, когда Давид Гильберт сформулировал проблему, названную Entscheidungsproblem (нем. задача разрешения). Ее суть заключается в нахождении алгоритма, определяющего доказуемость данного утверждения из аксиом с использованием правил логики. По названию очевидно, что это задача является задачей разрешения (выводит «да» или «нет»).
В ходе решения этой проблемы потребовалось определить термины «алгоритм» и «вычислимая функция». В 1936 году Алонзо Чёрч и Алан Тьюринг независимо показали, что общее решение Entscheidungsproblem невозможно, предположив, что интуитивное понятие «эффективная вычислимость» соответствует вычислимости функции на машине Тьюринга. Эта гипотеза сегодня известна как тезис Чёрча-Тьюринга.
20 марта 1956 в письме к Джону фон Нейману Курт Гёдель впервые поставил вопрос о вычислительной сложности. Гёдель интересовался, можно ли получить доказательство теоремы (в математико-логическом смысле слова) за квадратичное или линейное время. К сожалению, письмо было обнаружено лишь в 1989 году и получило широкую огласку, когда Юрис Хартманис опубликовал перевод и комментарий.
Статья Алана Кобэма 1965 года под названием «The intrinsic computational difficulty of functions» является одним из первых упоминаний класса сложности P, состоящего из разрешимых за полиномиальное время задач. Тезис Кобэма-Эдмондса (известный также как расширенный тезис Чёрча-Тьюринга), названный в честь Алана Кобэма и Джека Эдмондса, утверждает, что любая разумная модель вычислений может быть выражена через другую модель с замедлением, не более чем полиномиальным по размеру входных данных. Кобэм предположил, что класс P может быть хорошим способом для описания множества реально вычислимых задач. Любая проблема, не содержащаяся в P, невозможна, но если задача реального мира может быть решена с помощью алгоритма, существующего в P, то такой алгоритм в конечном итоге будет открыт.
В 1965 году Юрис Хартманис и Ричард Стернс опубликовали статью «On the Computational Complexity of Algorithms», отмеченную премией Тьюринга. В ней даются более точные определения сложности алгоритма и класса сложности. Хартманис и Стернс определили класс сложности как совокупность всех задач, которые можно решить за установленные временные рамки. В их статье показано, что существует бесконечная иерархия классов сложности (например, задачи, для которых наиболее быстрый алгоритм имеет время, пропорциональное n, n log n, n^2, n^3, 2^n и т. д.), где небольшое увеличение временного интервала позволяет решать больше задач. Во второй статье Хартманис совместно с Филипом М. Льюисом показали, что подобная иерархия существует и для количества памяти (функция от размера входа) при решении задачи на машине Тьюринга.
В 1967 году Мануэль Блюм разработал аксиоматическую теорию сложности, которая основана на его собственных аксиомах (аксиомы Блюма), и получил важный результат — теорему об ускорении. До этого мы говорили по большей части о сложности алгоритма. Хотелось бы аналогичным образом определить и сложность задачи: например, какова сложность самого эффективного (по времени и емкости) алгоритма, решающего эту задачу. Теорема об ускорении гласит, что есть некоторые задачи, для которых не существует самого быстрого алгоритма, потому что любой алгоритм для такой задачи можно «ускорить», построив более быстрый алгоритм.
Точная формулировка проблемы равенства P и NP была представлена в 1971 году. Тогда американский ученый Стивен Кук и работавший независимо советский ученый Леонид Левин доказали, что существуют практически актуальные проблемы, которые являются NP-полными. В США Стивен Кук опубликовал статью «The complexity of theorem proving procedures», в которой формализовал понятия редукции за полиномиальное время и NP-полноты, а также доказал существование NP-полной задачи (задача выполнимости булевых формул, SAT). Теорема была независимо доказана Леонидом Левиным и, таким образом, получила название «теорема Кука-Левина».
В 1972 году Ричард Карп сделал рывок в знаменитой статье «Reducibility among Combinatorial Problems», в которой показал, что около 20 разнообразных задач из комбинаторики и теории графов, известных своей вычислительной трудностью, являются NP-полными.
В августе 2010 года Виней Деолаликар, работавший в исследовательском отделении Hewlett-Packard в Пало-Альто в Калифорнии, заявил, что разгадал загадку P vs NP. Он утверждал, что P не равняется NP, однако научное сообщество нашло в его доказательстве фатальную ошибку. В начале 2002 года SIGACT News провел опрос среди 100 ученых, задав им вопрос о равенстве классов NP и P. 61 человек ответили, что «неравны», 9 — «равны», 22 затруднились ответить и 8 сказали, что гипотеза не выводима из текущей системы аксиом и, таким образом, не может быть доказана или опровергнута.
К чему приведет решение проблемы
Окей, теория вычислимости, формализация алгоритмов и абстрактные математические теории — все это конечно интересно, но как решение проблемы равенства NP и P классов отразится на практике? На самом деле, алгоритмы для решения NP-задач используются каждый день во многих сферах. Например, в криптографии, криптовалютах, восстановлении поврежденных файлов, системах блокировки спама, оптимизации в логистике и т. д. Более эффективные решения могли бы значительно сэкономить время и деньги, так как мы пользуемся в основном эвристическими методами, дающими лишь приближенные решения.
Однако существует и обратная сторона монеты. Солидная часть криптографии (криптосистемы с открытым ключом, технологии доказательства выполнения работы в блокчейне, системы блокировки спама) основывается на предположении о неравенстве NP и P классов. Если окажется, что некоторые задачи, для которых, как считалось, не существует эффективных алгоритмов, можно решать быстро, то многие методы защиты устареют.
Может оказаться и так, что последствия решения окажутся не такими тривиальными, как это часто и бывает в математике. В качестве примера рассмотрим континуум-гипотезу о существовании мощности, меньшей континуума и большей мощности счетного множества. Оказывается, существование такого кардинала нельзя ни доказать, ни опровергнуть в аксиоматике ZFC. Так что мы вправе считать, что такие мощности бывают (впрочем, как и считать, что не бывают). Однако ясно, что мы не можем конструктивно построить соответствующее множество. Возможно, точно также окажется и с алгоритмами для NP-задач в случае равенства NP и P (к слову, некоторые математики в опросе SIGACT News так и ответили: гипотеза не выводима из существующей системы аксиом, то есть не может быть доказана или опровергнута).
Пока что существующих методов доказательств недостаточно для строго математического ответа, но не нужно терять надежду. В марте 2001 года Ричард Карп предсказал, что проблема будет решена молодым математиком (до 30 лет) с использованием подхода, о котором еще никто не думал. Стивен Кук заявил, что кто-нибудь предоставит убедительное доказательство в ближайшие 20 лет.