Математическая логика и теория алгоритмов

в этом алгоритме рассмотрение каждого варианта, т.е. последо­ вательности соединенных дугами вершин vi, va v,3, ...v, „ требует n шагов. Следовательно, кансдая процедура ВЫБОР (иначе каждая копия алгоритма просмотра одного пути) работает не более, чем по­ линомиальное время, точнее имеет сложность порядка 0(и). Таким образом, задача выяснения существования в ориентированном графе гамильтонового цикла, длина которого меньше или равна М, является NP задачей. Детерминированная машина Тьюринга является частным случа­ ем недетерминированной машины Тьюринга (которая не имеет ко­ пий), поэтому имеем, что PQNP. Вопрос о том, будет ли P-NP, является открытой проблемой теории сложности. Широко распространено мнение, что РФЫР , сле­ довательно, Р а NP. Примеры задач из класса NP: 1) выяснение выполнимости формулы логики высказываний, записанной в к.н.ф.; 2) нахождение целочисленных решений системы линейных уравнений; 3) задача распознавания простого числа; 4) выяснение гамильтоновости графа; 5) задача коммивояжера; 6) размещение обслуживающих центров (телефон, телевиде­ ние, срочные службы) для максимального числа клиентов при мини­ мальном числе центров; 7) оптимальный раскрой (бумага, стальной прокат, отливка), оптимизация маршрутов в воздушном пространстве, инвестиций, ста­ ночного парка; 8) составление расписаний, учитывающих определенные условия; 9) оптимальная загрузка емкости (рюкзак, поезд, корабль, са­ молет) при некоторых условиях; 287