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

шем случае потребуется экспоненциальное количество времени и не будет возможности решить на практике такие задачи, за исключением очень малого числа индивидуальных задач. Первой задачей, для которой было доказано, что она является Л^Р-полной, была проблема о выполнимости (см. задачу 1 в § 4). Имеет место следующая теорема. Теорема 7.1 (теорема Кука). Задача выяснения выполнимости формулы логики высказываний, представленной в к.н.ф., является /\/Р-полной. Все приведенные ранее примеры ЛФ-задач (задачи 1-12) являются WP-полными задачами. Список Л'Р-полных задач в настоя­ щее время содержит несколько сотен задач и продолжает попол­ няться. Многие вновь установленные Л'Р-полные задачи печатаются в журнале Journal of Algorithms. В действительности о большей части задач комбинаторной оптимизации известна либо полиномиальная разрешимость, либо №-полнота, что является еще одним подтвер­ ждением гипотезы Р Ф NP. Как уже указано, считается, что алгоритм имеет полиномиаль­ ную временную сложность, если существует полином р(х) такой, что на любом входном слове длины п алгоритм завершает вычисления после выполнения не более чем р(п) операций. Если такого полинома не существует, временная сложность считается эксп Таким образом, для них число операций возрастает быстрее значений любого полинома. Кроме этого определения, существует и второе определение; алгоритм имеет экспоненциальную временную сложность, если .его временная слоясность имеет порядок не меньше, чем cct, где ОО, а (а > 1) - постоянные. Другими словами, временная сложность fiji) является § 6. Класс Е 290