В.А. Носов - Основы теории алгоритмов и анализа их сложности (курс лекций), страница 13

Проблемасостоит в том, чтобы найти алгоритм, который по любой такой формулеопределяет, истинна она или нет на натуральном ряду. Неразрешимость этойпроблемы установил Гедель К. (1931).2. Проблема разрешения для логики предикатов первого порядка. Нужнонайти алгоритм, который бы проверял общезначимость формулы алгебрыпредикатов. Норазрешимость этой проблемы установил Черч А. (1936).З. Проблема сочетаемости Поста. Конечное множество пар слов внекотором алфавите называется сочетаемым, если для некоторых пар(A1,B1),…,(As,Bs) из V выполнено равенство A1…As=B1…Bs . Нужно найтиалгоритм, который по всякому множеству V пар слов узнает сочетаемо оно илинет. Неразрешимость данной проблемы установил Пост Э.

(1946).4. Проблема представимости матриц. Рассматриваются ( n × n )-матрицынад кольцом целых чисел Z.Пусть даны произвольные матрицы U 1,...,U q и U .Нужно иметь алгоритм, который бы решал, верно ли U = U i1 ...U i p для74некоторых i1,..., i p .Неразрешимость данной проблемы, начиная с n=4 ,установлена Марковым А.А.(1958).5. Проблема тождества элементарных функций вещественногопеременного. Определим класс термов τ индуктивно: x - переменная, π -числотермы. Если u,v - термы, то (u + v ),(uv ),( u ),sin u, u - термы. Нужно иметьvалгоритм, который по любым двум термам из τ узнает, задают ли одну и тужефункцию одного вещественного переменного x. Неразрешимость даннойпроблемы установил Матиясевич Ю.В.

(1973).6. Проблема полноты автоматных базисов. Дан набор конечных автоматов(базис) в одним множеством входов и выходами, входящими в множествовходов. Строятся схемы с помощью присоединения базисного автомата ивведенияобратной связи. Каждая схема реализует автомат. Если схемами в данном базисеможет быть реализован любой автомат, в данном алфавите, то базис называетсяполным, в противном случае - неполным. Проблема полноты заключается в том,чтобы узнавать по заданному базису - является он полным или нет.Неразрешимость данной проблемы установилКратко М.И.

(1966).7. Десятая проблема Гильберта из 23 поставленных им в 1900 годуформулируется тая: "Пусть задано диофантово уравнение (т.е. уравнение видаp( x1,..., x n ) = 0 , p - многочлен) с произвольными неизвестными и целымирациональными коэффициентами. Указать способ, при помощи котороговозможно после конечного числа операций установить, разрешимо ли уравнениев целых рациональных числах".Неразрешимость 10-й проблемы Гильберта установлена МатиясевичемЮ.В.(1970). Учитывая важность данного результата, приведем его точнее.Пусть p( x1,..., x n , y1,..., y m ) - многочлен над кольцом целых чисел Z. Тогдапредикат M ( x1,..., x n ) задаваемый формулойM ( x1,..., x n ) = ∃ y1...

∃ y m( p( x1,..., x n , y1,..., y m ) = 0)называется диофантовым предикатом. (Область определения кванторов множество N0 ).Легко убедиться, что диофантовы предикаты являются полувычислимыми.Матиясевич Ю.В.в 1970 году установил:Теорема.Каждый полувычислимый предикат диофантов.Покажем теперь, как из этой теоремы следует неразрешимость десятойпроблемы Гильберта. Заметим, что если 10-я проблема Гильберта разрешима, торазрешима и такая проблема: "установить, имеет ли произвольноеполиномиальное уравнение p( x1,..., x n ) = 0 с целыми коэффициентами решение75в множестве натуральных чисел”. Действительно, любое натуральное числоможет быть представлено как сумма четырех квадратов (по теореме Лагранжа),поэтому, чтобы решать эту проблему достаточно найти целые решения22222222уравнения p( s1 ,t1 ,u1 , v1 ,..., s n ,t n ,u n , v n ) = 0Возьмем теперь многочлен p( x , y1,..., y m ) , такой,что x ∈W x ⇔ ∃y1,..., ∃y m ( p( x , y1,..., y m ) = 0) ,что можно сделать по теоремеМатиясевича.

Тогда если бы существовала разрешающая процедура для десятойпроблемы Гильберта, то существовала бы и разрешающая процедура дляпроблемы “ x ∈W x ” : чтобы проверить, верно ли a ∈W a , нужно проверить,имеет ли решение в N0 уравнение q( y1,..., y m ) = p( a, y1,..., y m ) . Значит,неразрешимая проблема “ x ∈W x ” сводится к проблеме Гильберта, что означаетее неразрешимость.Укажем еще одно следствие теоремы Матиясевича.Теорема.Всякое рекурсивно перечислимое множество является множествомнеотрицательных эначенй, принимаемых некоторым многочленом p( x1,..., x n )над кольцом целых чисел Z (причем x1,..., x n ∈ N 0 ).Док-во.Пусть А - рекурсивно перечислимое множество. По теореме Матиясевичасуществует многочлен q( x , y1,..., y m ) ,такой чтоx ∈ A ⇔ ∃y1,..., ∃y m ( q( x , y1,..., y m ) = 0) .Рассмотрим теперь многочлен p( x , y1,..., y m ) определяемый формулойp( x , y1,..., y m ) = x − ( x + 1)( q( x , y1,..., y m ))2Ясно, что p( x , y1,..., y m ) ≥ 0 ⇔ q( x , y1,..., y m ) = 0 причем в этом случаеp( x , y1,..., y m ) =x.

Таким образом,А есть множество неотрицательных значений, принимаемых p( x , y1,..., y m )когда x , y1,..., y m пробегает множество N0 .ч.т.д.Одно на приложений этого результата - множество простых чисел. Ясно,что множество простых чисел - рекурсивно перечислимо. На основаниидоказанного множество простых чисел есть множество положительныхзначений, принимаемых некоторым многочленом с целыми коэффициентами.Данный факт считался ранее маловероятным и даже невозможным.76§ 12 Характеристики сложности вычислений10 ) В общей теории алгоритмов изучается лишь принципиальная возможностьалгоритмического решения задачи. При рассмотрении конкретных задач необращается внимания на ресурсы времени и памяти для соответствующих имразрешающих алгоритмов. Однако нетрудно понять, что принципиальнаявозможность алгоритмического решения задачи еще не означает, что оно можетбыть практически получено. Поэтому возникает потребность уточнить понятиеалгоритмической разрешимости, введя характеристики слабости алгоритмов,позволяющие судить об их практической реализуемости.

Выше былоустановлено, что различные алгоритмические модели приводят к одному и томуже классу алгоритмически вычислимых функций. В то же время ясно, что выборалгоритмической модели, реализующей алгоритмы, существенно влияет насложность вычислений. Утверждения о трудоемкости вычислений, вообщеговоря, не сохраняются при изменении алгоритмической модели. Однако,имеется ряд фактов, которые не зависят от вычислительной модели и относятся ктак называемой машинно-независимой теории сложности.Введем необходимые определения, отправляясь от машины Тьюринга вкачестве модели вычислительного устройства. Пусть машина Тьюринга Твычисляет словарную функцию f ( x ) .

Определим функцию tT ( x ) , равнуючислу шагов машины Т , выполненному при вычислении f ( x ) , если f ( x )определено. Если f ( x ) не определено, то значение tT ( x) считаетсянеопределенным. Функция tT ( x) называется временной сложностью.Активной зоной при работе машины Т на слове x называется множествовсех ячеек ленты, которые содержат непустые символы, либо посещались впроцессе вычисленияf ( x ) головкой машины Т.

Определим функцию sT ( x ) , равную длине активнойзоны при работе машины Т на слове x , если f ( x) определено. Если f ( x ) неопределено, то значение sT ( x ) считается неопределенным. Функция sT ( x )называется емкостной (ленточной) сложностью.Теорема 1.Пусть машина Тьюринга Т имеет внешний и внутренний алфавит мощности kи r соответственно. Тогда для функций сложности sT ( x ) , tT ( x ) справедливыоценкиsT ( x ) ≤ x + tT ( x )(1)tT ( x ) ≤ rsT2 ( x ) k sT ( x )Док-во.В начальный момент на ленте записано слово x длины x . На каждом шагеактивной становится не более одной новой ячейки, поэтому sT ( x ) ≤ x + t T ( x ) .Найдем теперь число различных конфигурацийK = a (1) ... a (i −1) q j a (i ) ...

a ( s ′ ), s′ ≤ s77с активной зоной s′ , не превосходящей фиксированной величины s . Имеетсяk s′ ≤ k s вариантов записи на ленте, r вариантов выбора положения головки и sвариантов для значения длины s′ конфигурации K. Таким образом, числорассматриваемых конфигураций не превосходит rs2 k s . Далее, если впроцессе работы машины встретятся две одинаковые конфигурации, то машиназациклиться, поскольку конфигурация однозначно определяет следующую заней. Значит, если машина в процессе вычисления использует зону sT ( x ) , точисло ее шагов не превосходит числа различных конфигураций с зоной неs ( x)превышающей sT ( x ) .В итоге получаем неравенство tT ( x ) ≤ rsT2 ( x ) k Tитеорема доказана.ч.т.д.Введенные функции сложности sT ( x ) и tT ( x ) являются словарными.Удобно ввести для рассмотрения функции натурального аргумента, положивt T ( n) =sT (n) =max t T ( x )x =nmax sT ( x )x =n(2)Они также называются функциями временной и емкостной сложности (похудшему случаю).

Поведение этих функций в пределе при увеличении размеразадачи n называется асимптотической временной (соответственно - емкостной)cложностью. Для конкретных задач находятся, как правило, асимптотическиефункции сложности,Заметим, что для введенных функций sT ( x ) и tT ( x ) выполнены свойства:1) D(t T ( x )) = D( f T ( x ))(Здесь D( gT ( x )) - область определения функции g ( x ) , f T - функция,вычисляемая машиной Т ).2) Предикат P(x,y) определены соотношениемP( x , y ) ≡ (tT ( x ) = y ) - разрешим. (Аналогично для функции sT ( x ) ).Подобным образом можно определить функции сложности вычисления намашине МПД. Пусть Р - программа МПД. Обозначим через t P ( x ) функциюопределенную условием t P ( x) = µ t( P( x) ↓ за t шагов.) т.е.