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

S <—{2,3,... ,n} {Множество вершин, которые нужно посе­ тить} Длина пути О {Общая длина пути} nv< — 1 { Число пройденных вершин} {Пусть преемник (Vnv) обозначает допустимое, (не содержа- ш,ее паразитных циклов) множество вершин, в которые можно попасть из Vnv) whi le преемник (Vnv) begin Vnv-i ВЫБОР (^преемник nv< —nv+l; Длина пути Длина пути +длина дуги (Vnv-i, Ут) end if ш=п and Длина пути < Мthen успех else неудача end В этом алгоритме рассмотрение каждого варианта, т.е. последовательности соединённых дугами вершин vi, Vi2, Vi3,...Vin требует п шагов. Следовательно, каждая процедура ВЫБОР (иначе каждая копия алгоритма просмотра одного пути) работает не более, чем полиномиальное время, точнее имеет сложность порядка 0(п). Таким образом, задача выяснения суш,ествования в ориентиро­ ванном графе гамильтонового цикла, длина которого меньше или равна М, яв­ ляется NP задачей. Детерминированная машина Тьюринга является частным случаем неде­ терминированной машины Тьюринга (которая не имеет копий), поэтому имеем, чтоР ^ Р . Вопрос о том, будет ли P=NP, является открытой проблемой теории слож­ ности. Широко распространено мнение, что РфМР, следовательно, PczNP. Вопрос будет ли P=NP можно поставить следуюш,им образом. Если на ка­ кой то вопрос есть ответ и его можно проверить быстро, то верно ли, что и ответ этот можно найти так же быстро. Примеры задач из класса 1) выяснение выполнимости формулы логики высказываний; 2) выяснение гамильтоновости графа; 3) нахождение целочисленных решений системы линейных уравнений; 4) задача распознавания простого числа; 5) задача коммивояжёра; 6) размеш,ение обслуживаюш,их центров (телефон, телевидение, срочные службы) для максимального числа клиентов при минимальном числе центров; 226