Реферат по высшей математике на тему Равенство классов P и NP

Введение
Любой образованный человек наслышан о знаменитых нерешённых семи задачах. Это, так называемые, задачи тысячелетия.
Равенство классов P и NP, Гипотеза Пуанкарэ, Гипотеза Ходжа, Гипотеза Римана, Теория Янга-Миллса, существование и гладкость решений уравнений Навье-Стокса, Гипотеза Бёрча-Свиннертон-Дайера.
Задачи тысячелетия от носятся к списку открытых математических проблем. То есть, задачи были рассмотрены учёными, представляющими математические науки, и, скорее всего, верны, но не были доказаны. А без доказательств теории и догадки бессмысленны.
Многие математики всего мира борются за успех в решении хотя бы одной из них. Это не просто мотивация за звание лучшего: за решение одной задачи из списка Институт Клея даёт награду – 1 млн долл. США.
Стоить отметить, что одна из задач тысячелетия доказана: Гипотеза Пуанкарэ. И пришёл к её доказательству наш соотечественник – Г.Я. Перельман в 2002 году опубликовал исследование, из которого следует, что Гипотеза Пуанкарэ справедлива. Однако, награду наш математик забрать отказался. Теперь Пуанкарэ уже не гипотеза, а теорема.
На данный момент, уделим внимание первой из задач: равенство классов P и NP.
1. Алгоритмы и их эффективность
Часто, сами того не замечая, люди оперируют в обычной жизни гигантским количеством различных алгоритмов. Причём, значительная часть этих алгоритмов является сложной системой.
Естественно, современному человеку важно распределять свои силы эффективно. Что же это определяет? Человеку важно время, затраченное на определённый алгоритм и эффективность, которую этот алгоритм породил. Иными словами: в алгоритме должна быть задействована минимальная доля памяти, а его воспроизводство прошло максимально быстро. Именно время и память зависят от того, в каком размере нам поступают входные данные, которые должны быть подвергнуты алгоритму.
Таким образом, время обработки входных данных для свершения алгоритма напрямую зависит от объёма тех данных, которые задаются изначально. Следовательно, именно время работы алгоритма и объём потребляемой памяти анализируются при различных объёмах входных данных в рамках теории алгоритмов.
Эту зависимость мы выражаем в виде математической функции. Разумеется, данные зависимости описываются двумя разными функциями: одна для времени работы, другая для количества потребляемой памяти [1].
Например, время работы программы описывается линейной функцией. Это будет означать, что, если объём входных данных увеличится в 3 раза, время работы программы также возрастет в 3 раза. Если же, к примеру, зависимость времени работы от размера входных данных описывается квадратичной функцией, то при увеличении объёма входных данных в 3 раза время работы алгоритма возрастает в 9 раз.
Если зависимость времени работы программы от объёма входных данных описывается линейной, квадратичной, кубической и другими функциями, мы говорим о полиномиальном времени работы. Причина довольно простая: линейная, квадратичная, кубическая и так далее функции являются полиномами, то есть многочленами от некоторого числа переменных.
Стоит отметить, что время работы программы может иметь не только полиномиальную зависимость от объема входных данных. Характер роста может быть куда более взрывным. Классический пример: экспоненциальная зависимость, при которой увеличение входных данных всего на 1 единицу измерения повлечёт увеличение времени работы алгоритма в некоторое константное количество раз.
Пример экспоненциальной зависимости: рост популяции людей.
Опять же упрощая, можно сказать, что полиномиальные алгоритмы — это быстрые алгоритмы, а те же экспоненциальные — нет