💸 Как сделать бизнес проще, а карман толще?

Тот, кто работает в сфере услуг, знает — без ведения записи клиентов никуда. Мало того, что нужно видеть свое раписание, но и напоминать клиентам о визитах тоже. Проблема в том, что средняя цена по рынку за такой сервис — 800 руб/мес или почти 15 000 руб за год. И это минимальный функционал. Нашли самый бюджетный и оптимальный вариант: сервис VisitTime.
⚡️ Для новых пользователей первый месяц бесплатно. А далее 290 руб/мес, это в 3 раза дешевле аналогов. За эту цену доступен весь функционал: напоминание о визитах, чаевые, предоплаты, общение с клиентами, переносы записей и так далее.
✅ Уйма гибких настроек, которые помогут вам зарабатывать больше и забыть про чувство «что-то мне нужно было сделать».
Сомневаетесь? нажмите на текст, запустите чат-бота и убедитесь во всем сами!

Наибольшие размеры задач, решаемых за один час

Заметим, что для функции T_А (n) = 2 ⁿ увеличение скорости вычислений в 1000 раз приводит к тому, что размер наибольшей решаемой за 1 час задачи возрастает только на 10, в то время как при квадратичной функции временной сложности этот размер увеличивается более чем в 30 раз.

Задачу будем называть труднорешаемой, если для нее не существует полиномиального по верхней оценке временной вычислительной сложности решающего алгоритма.

Следует отметить, что между понятиями «труднорешаемая задача» и «задача, неразрешимая в реально приемлемом времени» нельзя ставить знак тождества. Различие между эффективными и неэффективными алгоритмами может иметь иной характер, если размеры решаемых задач невелики (функция T ₁(n) = 2 ⁿ, например, принимает при n ≤ 20 меньшие значения, чем функция T ₂(n) = n ⁵). Кроме того, широко известны некоторые имеющие экспоненциальную сложность алгоритмы, хорошо зарекомендовавшие себя в практике решения задач средних и даже больших размеров. Это объясняется тем, что временная сложность T(L) определена как верхняя граница числа необходимых операций при любом входе объема L, включая и наихудший возможный случай; именно на наихудший случай ориентирована оценка T (L). Оценка же «в среднем» может иметь существенно меньший порядок роста. Такова, в частности, ситуация с симплекс-методом для решения задач линейного программирования; только в среднем этот метод дает полиномиальную оценку времени счета.

Остановимся на вопросе установления труднорешаемости, т.е. определения невозможности построения для рассматриваемой задачи полиномиального по верхней оценке временной вычислительной сложности алгоритма решения. Будем рассматривать два класса дискретных задач – задачи оптимизации и задачи распознавания.

В каждой задаче распознавания считается определенным некоторый универсум U, в котором выделено подмножество V; по произвольному элементу х из U требуется определить, принадлежит ли х подмножеству V. Приведем два примера.

Пусть U – множество всех натуральных чисел, а подмножество V является совокупностью всех простых чисел. По натуральному числу х требуется определить, является ли оно простым.

Пусть U – множество всех конечных графов, а подмножество V является совокупностью всех гамильтоновых графов. По конечному графу G требуется определить, является ли он гамильтоновым.

Решить задачу распознавания означает ответить «да» или «нет» на поставленный вопрос. В случае, если в задаче распознавания правильным является ответ «да», будем говорить, что эта задача имеет положительное решение.

Для ряда задач распознавания полиномиальные по верхней оценке временной вычислительной сложности алгоритмы известны. В качестве примеров приведем задачу определения по сети с ограниченными пропускными способностями дуг, возможен ли в ней поток заданной мощности, и задачу определения по графу, является ли он эйлеровым. Для многих других задач, в том числе важных с точки зрения приложений, таких алгоритмов построить не удалось. К последним относятся, в частности, следующие задачи.

1. Выполнимость конъюнктивной нормальной формы. Задана конъюнктивная нормальная форма (КНФ) F от n переменных. Требуется определить, является ли F выполнимой (КНФ выполнима, если существует набор логических значений переменных, обращающий ее в истину).

2. Трехмерное сочетание. Дано множество М ⊂ X × Y × Z, где X, Y, Z – непересекающиеся множества, каждое из которых состоит из равного числа элементов q. Требуется определить, содержится ли в М состоящее из q элементов подмножество М' такое, что любые два элемента из М' не имеют ни одной равной координаты.

3. Вершинное покрытие. Заданы n -вершинный граф G и натуральная константа k, k< n. Требуется определить, можно ли в заданном графе выделить k- элементное подмножество вершин М такое, что каждое ребро графа имеет по меньшей мере одним своим концом вершину из М.

4. Клика. Заданы n -вершинный граф G и натуральная константа k, k< n. Требуется определить, имеется ли k- элементное подмножество вершин данного графа М такое, что любые две вершины из М соединены ребром.

5. Гамильтонов цикл. Задан конечный граф G; требуется определить, имеется ли простой (т. е. без самопересечений) цикл, проходящий через все вершины этого графа.

6. Разбиение. Заданы конечное множество А и «веса» v (а) всех элементов этого множества; указанные веса являются натуральными числами. Весом любого подмножества М, М ⊆ А, называем сумму весов входящих в М элементов. Требуется определить, можно ли разбить совокупность А на два подмножества равного веса.

Для всех перечисленных задач распознавания известны имеющие экспоненциальную временную сложность решающие алгоритмы. В то же время ни для одной из этих задач не удалось построить алгоритма с полиномиально зависящей от размера входной информации верхней оценкой числа выполняемых им элементарных операций.

Задачу распознавания «α ∈ P?» назовем полиномиально сводимой к задаче распознавания «β ∈ Q?», если существует вычислимая в полиномиальном времени функция ϕ такая, что α ∈ P тогда и только тогда, когда ϕ (α) ∈ Q. Задачи распознавания «α ∈ P?» и «β ∈ Q?» считаются полиномиально эквивалентными, если задача «α ∈ P?» полиномиально сводима к " β ∈ Q? ", а задача «β ∈ Q?» полиномиально сводима к " α ∈ P? ".

Если задача «α ∈ P?» полиномиально сводима к задаче «β ∈ ∈ Q?» и задача «β ∈ Q?» имеет полиномиальную временную сложность, то временная сложность задачи «α ∈ P?» также полиномиальная.

Перечисленные выше задачи распознавания 1–6 полиномиально эквивалентны. Поэтому наличие полиномиального решающего алгоритма для любой из них автоматически влечет разрешимость в полиномиальном времени каждой из остальных задач.

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

Рассмотрим концепцию недетерминированной машины Тьюринга (НДМТ). В процессе работы НДМТ могут возникать ситуации, когда имеется возможность реализации одного из нескольких элементарных действий. Недетерминированные машины Тьюринга предназначаются исключительно для решения задач распознавания. Считается, что недетерминированная машина дает положительный ответ, если для заданного входного слова (оно является записью входной информации по решаемой задаче) существует способ работы данной НДМТ такой, что в итоге машина оказывается в специально выделенном положительном заключительном состоянии.

Существенным является следующий факт. Для каждой из перечисленных задач 1–6 можно построить решающую ее НДМТ, функционирующую в полиномиально зависящем от объема входной информации времени. При решении любой из задач 1–6 НДМТ работает в два этапа. Первый этап – генерация подтверждения (подтверждение генерируется недетерминированным образом). Второй этап – проверка верности построенного подтверждения (на данном этапе машина функционирует детерминированно); если подтверждение верно, машина переходит в положительное заключительное состояние. Для иллюстрации рассмотрим задачу «Выполнимость КНФ», заключающуюся в определении по произвольной КНФ F (х₁, х₂, …, х_n), является ли данная формула выполнимой. Решающая эту задачу НДМТ (входным словом является формула F (х₁, х₂, …, х_n)) на первом этапе работы недетерминированным образом генерирует подтверждение, которое в данном случае представляет собой набор из нулей и единиц (в принципе, может быть напечатан любой набор символов 0 и 1). Далее первый напечатанный элемент подтверждения трактуется как логическое значение переменной х ₁, второй элемент – как логическое значение переменной х ₂, и т.д. Если число символов в подтверждении оказалось большим, чем n, то лишние символы роли не играют; если же символов недостает, то всем переменным, для которых в подтверждении соответствующих элементов не оказалось, приписывается значение 0. На втором, детерминированном этапе работы машина осуществляет проверку верности сгенерированного подтверждения, т.е. обращается ли в истину КНФ F при определенных описанным образом значениях ее переменных. Только в случае истинности КНФ машина переходит в положительное заключительное состояние. Оба этапа работы машины реализуются в полиномиально зависящем от объема входной информации времени. Машина дает положительный ответ (способ функционирования недетерминированной части машины, обеспечивающий в итоге ее переход в положительное заключительное состояние существует) тогда и только тогда, когда рассматриваемая КНФ выполнима.

При решении каждой из перечисленных задач 1–6 функционирование машины Тьюринга является недетерминированным только на первом этапе, где реализуется «угадывание» подтверждения. Фактически, недетерминированная машина Тьюринга решает проблему распознавания в полиномиальном времени тогда и только тогда, когда в полиномиальном времени, детерминированным вычислением можно проверить правильность кем-то указанного подтверждения.

Задача распознавания считается задачей класса NP, если она решается соответствующим образом построенной недетерминированной машиной Тьюринга за время, ограниченное значением полинома от объема определяющей задачу входной информации.

Задачи распознавания, разрешимые на детерминированных машинах Тьюринга за время, ограниченное значением полинома от объема входной информации, называются задачами класса P. Так как концепция недетерминированной машины Тьюринга является обобщением понятия детерминированной машины, класс задач P является подклассом класса задач NP, т.е. Р ⊆ NP.

Задачу распознавания именуем NP -полной, если:

1) она принадлежит классу NP;

2) к ней полиномиально сводима любая принадлежащая классу NP задача.

Установлено, что любая задача распознавания класса NP полиномиально сводима к задаче «Выполнимость КНФ». Таким образом, задача «Выполнимость КНФ» – пример NP -полной задачи.

Из того, что перечисленные выше, принадлежащие классу NP, задачи распознавания 1–6 полиномиально эквивалентны, делаем вывод: каждая из этих задач NP- полна. К настоящему времени число известных, имеющих существенный теоретический интерес и прикладное значение NP- полных задач исчисляется тысячами. Все NP -полные задачи полиномиально эквивалентны. Наличие полиномиального по верхней оценке временной вычислительной сложности решающего алгоритма для ка-кой-либо одной NP -полной задачи автоматически повлекло бы за собой полиномиальную разрешимость всех принадлежащих классу NP задач, включая NP- полные. Накопленный опыт решения дискретных задач, с учетом факта полиномиальной эквивалентности NP -полных задач, позволяет принять следующую гипотезу:

ДЛЯ NP-ПОЛНЫХ ЗАДАЧ ПОЛИНОМИАЛЬНЫХ ПО ВЕРХНЕЙ ОЦЕНКЕ ВРЕМЕННОЙ ВЫЧИСЛИТЕЛЬНОЙ СЛОЖНОСТИ АЛГОРИТМОВ РЕШЕНИЯ НЕ СУЩЕСТВУЕТ.

Отметим, что сформулированная гипотеза часто записывается в виде «Р ≠ NP». Формула «Р ≠ NP», означающая несовпадение классов задач Р и NP, как очевидно, эквивалентна утверждению, что для любой NP- полной задачи не существует решающего алгоритма, полиномиального по верхней оценке временной вычислительной сложности.

Выше понятие полиномиальной сводимости было введено только для задач распознавания. Расширим это понятие следующим образом. Будем говорить, что задача распознавания «α ∈ P?» полиномиально сводится к задаче оптимизации Z, если по каждой индивидуальной задаче «α ⁰ ∈ P?» за время, полиномиально зависящее от размера ее исходных данных, строится индивидуальная задача оптимизации Z ⁰ и определяется константа С такие, что задача Z ⁰ обладает решением, обеспечивающим значение критерия не хуже С (т.е. большее или равное С для за-дач максимизации, меньшее или равное С для задач минимизации) тогда и только тогда, когда исходная задача распознавания имеет положительное решение.

Задачу назовем NP - трудной, если к ней полиномиально сводится любая принадлежащая классу NP задача. Легко устанавливается, что бинарное отношение полиномиальной сводимости обладает свойством транзитивности. Поэтому для доказательства NP -трудности той либо иной задачи достаточно показать, что к этой задаче полиномиально сводится некоторая известная NP -полная задача.

Из гипотезы Р ≠ NP вытекает, что для NP -трудных задач полиномиальных по верхней оценке временной вычислительной сложности алгоритмов решения не существует.

Теорема 3.1. Классическая задача коммивояжера NP - трудна.

Доказательство заключается в полиномиальном сведении к классической задаче коммивояжера (ЗК) следующей NP -полной задачи «Гамильтонов цикл»: задан произвольный ориентированный граф G с множеством вершин {1, 2, …, n }; требуется определить, имеется ли в G простой, проходящий через все вершины графа цикл. По заданному графу G определяющую ЗК матрицу S (G) = { s_ij } размера n × n строим следующим образом. Все стоящие на главной диагонали элементы s_ii полагаем равными нулю; в случае i ≠ j считаем, что s_ij = 1, если дуга (i, j) в графе G имеется, и s_ij = 2, если дуги (i, j) в графе G нет; здесь i = 1,..., n, j = 1,..., n. В построенной задаче коммивояжера длина проходящего через все города кратчайшего замкнутого маршрута не может быть меньше n. Такой маршрут действительно имеет длину n тогда и только тогда, когда каждый реализуемый в нем элементарный переход имеет длину 1, т.е. когда каждый переход выполняется по дуге исходного графа G. В свою очередь, это возможно тогда и только тогда, когда граф G гамильтонов. Таким образом, решив определяемую матрицей S (G) задачу коммивояжера, мы можем ответить на вопрос, является ли граф гамильтоновым. Граф G гамильтонов тогда и только тогда, когда оптимальное значение критерия в определяемой матрицей S (G) задаче коммивояжера равно n. Теорема доказана.

В предположении Р ≠ NP задача коммивояжера не может иметь полиномиального решающего алгоритма, ибо в против-ном случае за полиномиальное время решалась бы задача «Гамильтонов цикл».

В выполненном доказательстве получен более сильный результат, чем сформулированный в теореме. Показано, что NP -трудным является частный подкласс задач коммивояжера, в которых длины элементарных переходов принимают значения только из множества {1, 2}.

Кроме ЗК из выше рассмотренных к числу NP -трудных относятся, в частности, также задача о ранце (данный факт доказывается путем описанного в главе 1 сведения к задаче о ранце NP -полной задачи «Разбиение»), задачи Джонсона для трех и более станков, каноническая задача однопроцессорного обслуживания потока заявок.

Отметим, что согласно имеющимся определениям каждая NP- полная задача NP -трудна. В совокупности NP -трудных задач NP -полные задачи образуют наиболее простой частный подкласс.

Любая задача оптимизации индуцирует соответствующую ей задачу распознавания. В частности, задача максимизации критерия К (х) при х ∈ D порождает задачу распознавания, в ко-торой по начальным данным исходной задачи максимизации и константе С требуется определить, имеется ли в D элемент х* такой, что К (х*) ≥ С. Задача минимизации критерия К (х) при х ∈ ∈ D порождает задачу распознавания, в которой требуется определить, имеется ли в D элемент х* такой, что К (х*) ≤ С. Очевидно, что из NP -полноты индуцированной задачи распознавания следует NP -трудность исходной задачи оптимизации.

***

Алгоритм А решения задачи Z с целочисленными начальными данными назовем псевдополиномиальным, если верхняя оценка количества выполняемых им элементарных операций T_А не превышает значения некоторого полинома от двух переменных Р_А(L,), где L – объем входной информации по задаче Z, а – максимальное из чисел в ее составе. ZMZM

Пусть Z - произвольная массовая задача, а Р(х) - полином с целыми коэффициентами. Через Z(Р) будем обозначать совокупность входящих в Z индивидуальных задач, в которых не превышает Р(ZMV).

Задача Z называется NP - полной (NP - трудной) в сильном смысле, если:

1. она является NP - полной (NP - трудной);

2. существует такой полином Р, что задача Z(Р) также NP - полна (NP - трудна).

Из приведенного определения вытекает, что если задача Z NP - полна и не является задачей с числовыми параметрами, то Z - NP - полная в сильном смысле задача. Получаем, что из перечисленных выше задач распознавания 1 – 6 первые пять задач (" Выполнимость КНФ", " Трехмерное сочетание", " Вершинное покрытие", " Клика", " Гамильтонов цикл") - полны в сильном смысле. NP

Из гипотезы NP ≠ P следует, что для NP -полных в сильном смысле и NP -трудных в сильном смысле задач псевдополиномиальных решающих алгоритмов не существует.

Отметим, что рассмотренный в главе 1 алгоритм Акзр решения m -мерной задачи о ранце с n предметами (34) - (36) псевдополиномиален. Действительно, верхней оценкой числа выполняемых этим алгоритмом элементарных операций является Сmn(W+1)^m, где W – максимальное из чисел, записанных в правых частях линейных ограничений (35), а С – константа, не зависящая от конкретных характеристик задачи. Из приведен-ной оценки следует, что число выполняемых алгоритмом элементарных операций не превышает СL(М+1)^m, где L – объем входной информации по задаче, М – максимальное из чисел в ее составе, а С – константа, не зависящая от определяющих задачу параметров. Полученная оценка – полином от переменных L и М степени m+1. Таким образом, m-мерная задача о ранце NP -трудна, но не в сильном смысле.

NP -полная задача " Разбиение" легко сводится к одно-мерной задаче о ранце и имеет поэтому псевдополиномиальный решающий алгоритм. Таким образом устанавливаем, что задача " Разбиение" NP -полна, но не в сильном смысле.

***

Известно, что NP -полной в сильном смысле является следующая задача «3-Разбиение»: множество М состоит из 3 n элементов, каждый элемент х из М имеет вес v (х), суммарный вес всех элементов множества М равен nV, веса всех элементов и V – натуральные числа; спрашивается, можно ли разбить множество М на n попарно непересекающихся трехэлементных подмножеств так, чтобы суммарный вес элементов каждого под-множества оказался равным V.

Задача сохраняет NP -полноту в сильном смысле и при следующем дополнительном условии: для каждого х из М имеет место (V /4) < v (х) < (V /2).

Отметим ряд дополнительных фактов. Задача линейного программирования полиномиально разрешима (в то время как обычно используемый для ее решения симплекс-метод по верхней оценке временной вычислительной сложности полиномиальным не является), задача целочисленного линейного программирования NP -трудна в сильном смысле. NP -трудными в сильном смысле являются все рассмотренные выше варианты задачи коммивояжера и каноническая задача однопроцессорного обслуживания потока заявок.

Следует заметить, что наряду с анализом гарантированного функционирования алгоритмов значительный интерес представляют оценки их поведения «в среднем». Отличие здесь может быть принципиальным. В частности, доказано, что в среднем симплекс-метод решает задачи линейного программирования в полиномиальном времени и быстрее чем известные алгоритмы решения этой задачи с гарантированно полиномиальной верхней оценкой трудоемкости вычислений.