Логика предикатов является развитием логики высказываний. Она содержит в себе логику высказываний, т.е. элементарные высказывания, разглядываемые как величины, каковые принимают значения И или Л. Но кроме этого, язык логики предикатов вводит в рассмотрение утверждения, которые содержат высказывания типа «для любого» и «существует», каковые обозначаются кванторами существования и всеобщности.
Опр. n-местный предикат – это отношение на декартовом произведении n множеств.
Содержательно эти n множеств смогут быть разными. Но, в случае, если забрать их объединение, то возможно взять некое множество M. Тогда n-местный предикат – это отношение на декартовом произведении n множеств М.
Одноместный предикат – это свойство.
К примеру, в случае, если N – множество натуральных чисел, то одноместный предикат четность P(x) принимает значение И (либо 1), в случае, если x –четное, а двухместный предикат больше P(x,y) принимает значение И (либо 1), в случае, если xy.
В случае, если же не будем фиксировать элемент множества М, к примеру, разглядим P(х), где х — любой элемент M,то возьмём некое предложение, которое делается высказыванием, в то время, когда х замещено определенным элементом M.К примеру, в случае, если M есть множеством всех натуральных чисел, а А(х) предикат простота числа, то предложение делается высказыванием, в случае, если х заменить числом, к примеру, 3 -простое число, 4-простое число. Наряду с этим приобретаем высказывания, каковые подлинны, или фальшивы. Следовательно, А(х) порождает отношение на множестве М.
Вводятся особые обозначения. Пускай M -множество, Р(х) — определенный на M одноместный предикат. Тогда выражение хР(х) свидетельствует: для всех х Р(х) либо для всех х выполняется Р(х), либо для любого х Р(х), либо для каждого х Р(х). Под выражением хР(х) подразумевается высказывание подлинное, в то время, когда Р(х) действительно для каждого х из M и фальшивое — в другом случае. Знак именуется квантором всеобщности. Выражение хР(х) свидетельствует существует х такое, что Р(х) либо хотя бы для одного х Р(х), либо для некоего х Р(х). Под выражением хР(х) подразумевается высказывание, которое действительно, в случае, если Р(х) принимает значение И хотя бы для одного значения переменной х из M, и ложно, в случае, если Р(х) для всех значений переменной х принимает значение Л. Знак именуется квантором существования.
Пускай Р(х1,х2,…,хп) -n-местный (п2) предикат.Выражение хiР(х1,х2,…,хп), 1 i n, есть (n-1)-местным предикатом, зависящим от (свободных) переменных х1,х2,…,хi-1,хi+1,…,хn, причем высказывание хiР(а1,а2,…,аi-1, хi,аi+1,…,аn) действительно тогда и лишь тогда, в то время, когда для любого значения а действительно высказывание Р(а1,а2,…,аi-1,a,аi+1,…,аn). Выражение хiР(х1,х2,…,хп), 1 i n, есть (n-1)-местным предикатом, зависящим от (свободных) переменных х1,х2,…,хi-1,хi+1,…,хn, причем высказывание хiР(а1,а2,…,аi-1, хi,аi+1,…,аn) действительно тогда и лишь тогда, в то время, когда для хотя бы одного значения а действительно высказывание Р(а1,а2,…,аi-1,a,аi+1,…,аn).
Квантор всеобщности есть обобщением (аналогом) конъюнкции, а квантор существования — обобщением (аналогом) дизъюнкции на произвольное, не обязательно конечное, множество значений переменной. В действительности, возможно было бы обойтись одним квантором, поскольку они выражаются приятель через приятеля, к примеру, выражение хА(x) эквивалентно выражению. ( х( А(x))).
Навешивание квантора по переменной х связывает переменную х. Понятие «связанная переменная» подобно понятиям: индекс суммирования в комбинаторике, переменная интегрирования в математическом анализе либо параметр цикла в программе. Вне суммы, интеграла либо цикла не имеет значения, какой буквой они обозначены. Наряду с этим, в случае, если такая же буква видится вне суммы, интеграла либо цикла, то это вторая буква с тем же обозначением. К примеру, в формуле
переменная x под интегралом и переменная x вне интеграла – это различные переменные.
Исходя из этого чтобы не было недоразумений одну из этих переменных переобозначают. Для определенности, допустим, что это связанная переменная. Такое переобозначение именуется правилом переименования связанных переменных.
Понятие формулы в исчислении предикатов требует некоторых предварительных замечаний. Буквы начала латинского алфавита (а,b,с,…) и они же с числовыми индексами (а1,а2,…,b1,b2,…,с1,с2,…) именуются предметными константами. Буквы финиша латинского алфавита (х,у,…) и они же с числовыми индексами (х1,х2,…,у1,у2,…,z1,z2,… ) именуются предметными переменными. Буквы An с числовыми индексами i 1, п 0, именуются предикатными буквами, а fin, i 1, п 1, — функциональными буквами. Верхний индекс предикатной либо функциональной буквы показывает число доводов, а нижний индекс помогает для различения букв с одним и тем же числом доводов.
Числовые индексы у предикатных и функциональных букв довольно часто опускаются, если они понятны из контекста. К примеру, вместо (х,у) пишут А1(х,у), и в случае, если нет вторых двухместных предикатных букв А Вместо А1(х,у) пишут А(х,у), в случае, если другие предикаты обозначаются вторыми буквами.
Определение терма:
а) любая предметная переменная либо предметная постоянная имеется терм;
б) в случае, если fin — функциональная буква и t1,t2,…,tn — термы, то fin (t1,t2,…,tn) имеется терм;
в) выражение есть термом лишь в том случае, если это направляться из правил а) и б).
Примеры термов: а, х1, f (х,а), G (а, f (у)).
Предикатные буквы, примененные к термам, порождают элементарные формулы, либо правильнее: в случае, если Ain — предикатная буква, а t1,t2,…,tn — термы, то — элементарная формула. Наряду с этим считается, что нульместная предикатная буква также есть элементарной формулой.
Примеры элементарных формул: A1, A1 (х1,а1), А1(f(х)), А3(a,x,f(х,y,b)).
Определение формулы требует фиксации некоего базиса (полной совокупности логических связок). Классический пример выглядит следующим образом.
светло синий. Формулы логики предикатов определяются следующим образом:
а) любая элементарная формула имеется формула;
б) в случае, если А и В — формулы и х — предметная переменная, то каждое из
выражений ( А), (АВ), ( хА) имеется формула;
в) выражение есть формулой лишь в том случае, если это
направляться из правил а) и б).
Отдавая дань классическим обозначениям и определения, мы применяли полную совокупность логических связок ( ,) -отрицание, импликация. Но вместо этого возможно применять любую другую полную совокупность логических связок (функций). (Вспомните теорему Поста.) Исходя из этого в формулах исчисления предикатов употребляются каждые логические связки, в силу того, что подразумевается, что их в любой момент возможно выразить через полную совокупность функций ( ,).
Опр. Протяженность l(F) формулы F – это количество входящих в ее запись логических связок и букв.
Для сокращения количества скобок действует простое старшинство связок, а кванторы, к примеру, идут по старшинству по окончании связок: отрицание, конъюнкция, дизъюнкция, но перед эквивалентностью и импликацией.
В выражениях ( хА) и ( хА) формула А именуется областью действия кванторов х и х соответственно.
Договоримся кроме этого опускать скобки, в каковые содержится формула А в формулах вида (Q1(Q2(…))), где Q1 и Q2 … -любые кванторы. К примеру, вместо
( х( у( z(A1 (х,у,z))))) пишут х у zA1 (х,у,z).
Вхождение переменной х в данную формулу именуется связанным, в случае, если х есть переменной входящих в эту формулу кванторов х, х либо находится в области действия входящих в эту формулу кванторов х, х; в другом случае вхождение переменной х в данную формулу именуется свободным. К примеру, вхождение переменной х в формулу у A1 (х,у)=A2 (у,у) есть свободным, второе и первое вхождение переменной у — связанное, а четвёртое вхождение и третье у в эту формулу -свободное. Так, одинаковая переменная в одной и той же формуле может иметь как связанные, так и свободные вхождения. (Это , что одной буквой обозначены различные сущности.) Переменная именуется свободной (связанной) переменной в данной формуле, в случае, если существуют свободные (связанные) ее вхождения в эту формулу.
Формула именуется замкнутой, если она не содержит никаких свободных переменных, т.е. или все ее переменные связанные, или переменных нет совсем. Нам в будущем потребуется понятие выполнимых и общезначимых формул исчисления предикатов. А эти понятия определяются через понятие интерпретации.
Интерпретацию будем вычислять заданной, в случае, если:
1. Задано непустое множество М,именуемое областью интерпретации.
2. Заданы следующие соответствия:
- предикатным буквам An поставлены в соответствие кое-какие n -местные предикаты (отношения) в М;
- функциональным буквам fin поставлены в соответствие кое-какие n -аргументные функции, отображающие Мn в М;
- каждой предметной постоянной поставлен в соответствие некий (фиксированный) элемент из М;
- кванторам и логическим связкампоставлен в соответствие их простой суть.
К примеру, дабы задать интерпретацию для формулы xA(x,y,b1), необходимо задать множество М — область интерпретации (область трансформации переменных x,y). Из данной области М будем брать некий элемент, соответствующий предметной постоянной b1. Потом необходимо задать 3-х местный предикат на М,соответствующей предикатной букве A. Так, возможно положить, что М – множество натуральных чисел, предметной постоянной b1 поставить в соответствие 3, а A (x,y,z) поставить в соответствие предикат x + y z. Тогда формула xA(x,y,b1) в заданной интерпретации запишется: x(x + y 3)- и свидетельствует, что для любого натурального x сумма x + у больше 3. Разумеется, что это отношение действительно при некоторых у (у 2) и ложно при вторых значениях у (0 x(x +y 0) будет действительно при любом значении свободной переменной у.
Легко видеть, что для той же формулы xA(x,y,b1)возможно выстроить очень много вторых интерпретаций, выбирая разные множества М,выбирая из Мкаким-то образом элемент, соответствующий b1, и задавая разным образом на М трехместный предикат.
При данной интерпретации любая формула без свободных переменных (замкнутая формула) является высказыванием , которое действительно или ложно, а любая формула со свободными переменными высказывает некое отношение на М,которое возможно действительно для одних значений из М и ложно для других.
Опр. Формула именуется выполнимой в данной интерпретации, если она принимает значение И хотя бы для одной совокупности вероятных значений её свободных переменных (если они имеется). В случае, если формула не содержит свободных переменных, то она именуется выполнимой в том случае, если принимает значение И в данной интерпретации.
Опр. Формула именуется подлинной в данной интерпретации, если она принимает значение И для всех вероятных значений её свободных переменных (если они имеется). В случае, если же свободных переменных нет, то формула именуется подлинной, в то время, когда она принимает значение И в данной интерпретации.
Опр. Формула именуется фальшивой в данной интерпретации, если она принимает значение Л для всех вероятных значений её свободных переменных (если они имеется). В случае, если же свободных переменных нет, то формула именуется фальшивой, в то время, когда она принимает значение Л в данной интерпретации. Разумеется, что формула фальшива в данной интерпретации тогда и лишь тогда, в то время, когда она не выполнима в данной интерпретации. Так же ясно, что формула A выполнима в данной интерпретации тогда и лишь тогда, в то время, когда она не есть фальшивой в данной интерпретации.
Эта интерпретация именуется моделью для множества формул G, в случае, если любая формула из G подлинна в данной интерпретации.
Возможно доказать следующие особенности формул в данной интерпретации.
- Формула A фальшива в данной интерпретации тогда и лишь тогда, в то время, когда A подлинна в данной же интерпретации. Формула A подлинна в данной интерпретации тогда и лишь тогда, в то время, когда A фальшива в данной же интерпретации.
- Никакая формула не может быть одновременно истинной и фальшивой в одной и той же интерпретации.
- В случае, если в данной интерпретации подлинны A и AB, то действительно и B.
- Формула AB фальшива в данной интерпретации тогда и лишь тогда, в то время, когда A действительно в данной интерпретации, а B ложно.
- Формула AB выполнима в данной интерпретации тогда и лишь тогда, в то время, когда A и B принимают значение И в один момент хотя бы для одной совокупности значений собственных свободных переменных. В случае, если же свободных переменных нет, то формула AB выполнима в данной интерпретации тогда и лишь тогда, в то время, когда обе формулы A и B подлинны в данной интерпретации.
- Формула A B выполнима в данной интерпретации, в случае, если хотя бы одна из них выполнима в данной интерпретации.
- Формула A=B выполнима в данной интерпретации тогда и лишь тогда, в то время, когда A и B принимают значение И в один момент либо значение Л (также в один момент) хотя бы для одной совокупности значений собственных свободных переменных. В случае, если же свободных переменных нет, то формула A=B выполнима в данной интерпретации тогда и лишь тогда, в то время, когда A и B принимают однообразные истинностные значения в данной интерпретации.
- Формула хА выполнима в данной интерпретации тогда и лишь тогда, в то время, когда A принимает значение И хотя бы для одной совокупности значений её свободных переменных и хотя бы одного значения переменной x.
- Формула xA подлинна в данной интерпретации тогда и лишь тогда, в то время, когда в данной интерпретации действительно A.
- В случае, если формула A замкнута, то в данной интерпретации A свидетельствует некое высказывание (нет свободных переменных), следовательно, A действительно или ложно. В противном случае, в случае, если A замкнуто, то в любой данной интерпретации или действительно A, или действительно A.
Разглядим некую пропозициональную форму. В случае, если в пропозициональную форму вместо пропозициональных букв подставить формулы логики предикатов (вместо всех вхождений одной и той же пропозициональной буквы подставлять одну и ту же формулу), возьмём некую формулу, которая именуется частным случаем пропозициональной формы. Тогда легко доказать следующее утверждение. Каждый частный случай любой тавтологии подлинен в каждой интерпретации.
Опр. Формула логики предикатов именуется логически общезначимой, если она подлинна в любой интерпретации.
Логическая общезначимость формулы свидетельствует, что какую бы ни выбирали область интерпретации и какие конкретно бы соответствия не задавали, мы постоянно будем приобретать подлинные отношения либо высказывания.
Примером логически общезначимых формул, разумеется, являются следующие формулы: xA хА ; xA ? х А .
Опр. Формула логики предикатов A именуется выполнимой, в случае, если существует интерпретация, в которой выполнима A.
Примером выполнимой формулы есть вышеприведенная формула xA(x,y,b1).
Имеют место следующие очевидные утверждения.
1. Формула A логически общезначима тогда и лишь тогда, в то время, когда формула A не есть выполнимой.
2. Формула A выполнима тогда и лишь тогда, в то время, когда формула A не есть логически общезначимой.
Формулу логики предикатов A именуется несоответствием, в случае, если формула A есть логически общезначимой. (Формула A фальшива во всякой интерпретации.)
Говорят, что формула логики предикатов A логически влечет формулу логики предикатов B , в случае, если в любой интерпретации формула B принимает значение И при каждой совокупности значений свободных переменных (входящих в A и B), при которых формула A приняла значение И. В противном случае говорят, что B есть логическим следствием формулы A. Формулы A и B логики предикатов именуют равносильными (логически эквивалентными), в случае, если любая из них логически влечет другую. В случае, если формулы А и В равносильны, то, как и в логике высказываний, записываем: A ~В.
Следующие теоремы проливают свет на суть логических связок.
Теорема.Формула A логически влечет формулу B тогда и лишь тогда, в то время, когда формула A B логически общезначима.
Теорема.Формулы A и B равносильны (логически эквивалентны) тогда и лишь тогда, в то время, когда формула A?B логически общезначима.
Теорема 2.3.В случае, если формула A логически влечёт формулу B и A действительно в данной интерпретации, то в данной же интерпретации действительно и B.
Формула B именуется логическим следствием формул А1, А2, Ап, в случае, если в любой интерпретации формула B принимает значение И при каждой совокупности значений свободных переменных (входящих в B и А1, А2, ., Ап), при которых в один момент все формулы А1, А2, …, Ап приняли значение И. Иными словами говорят, что B есть логическим следствием формул А1, А2,…, Ап.
Замечание. Из приведенных теорем направляться, что , в случае, если мы применим правило преобразования связанных переменных, то возьмём логически эквивалентную исходной формулу, в которой уже одинаковая переменная не будет обозначать различные сущности.
При определении формулы исчисления предикатов мы фиксировали полную совокупность логических связок:( ,). Так как она полна, то через нее возможно высказывать остальные функции алгебры логики. Разумеется, что из теоремы Поста направляться, что для любой формулы существует логически эквивалентная формула, которая содержит лишь функции алгебры логики, входящие в фиксированную совокупность логических связок, использованную при определении формулы. В этом случае говорят, что эта формула имеет обычную форму.
Опр. Формула исчисления предикатов следующего вида: F=Qx1Q2x2…QnxnG, где Qx1, Q2x2,…,Qnxn – кванторы, а формула G не содержит кванторов, именуется формулой в предваренной (приведенной) обычной форме.
Легко из определения логических функций (конъюнкции, дизъюнкции, отрицания и импликации) сходу направляться утверждение.
Теорема. Для каждой формулы логики предикатов длины L в обычной форме со связками ( ,) существует логически эквивалентная (равносильная) ей формула в обычной форме со связками , имеющая длину constL.
В [3] приведено подтверждение следующей теоремы.
Теорема.Для каждой формулы логики предикатов в обычной форме со связками ( ,) существует логически эквивалентная (равносильная) ей формула в предваренной обычной форме.
Наряду с этим создатель не смотрит за длиной формул (она его не интересует). В случае, если дословно забрать это подтверждение и проследить за длинами формул, то мы заметим, что в действительности в доказано следующая теорема.
Теорема.Для каждой формулы длины L логики предикатов в обычной форме со связками ( ,) существует логически эквивалентная (равносильная) ей формула в предваренной обычной форме длины constL.
В действительности целый совершённый экскурс в теорию предикатов нам был нужен чтобы сформулировать следующее утверждение.
Теорема.Для каждой формулы F логики предикатов l(F) существует логически эквивалентная (равносильная) ей формула F* в предваренной обычной форме длины не более, чем kl(F), где k- некая константа.
В действительности справедливо более правильное относительно соотношения длин формул утверждение, но мы даем эту теорему без доказательства, а для ее применения при анализе класса нам достаточно данной формулировки.
Теорема 9.6. Задача выполнимости булевской формулы с кванторами PSPACE-полна.
Выше обращение шла о задаче выполнимости КНФ, т.е. рассматривалась булевская формула без кванторов. В этом случае речь заходит о булевских формулах вида
F(x)=Q1y1…QnynH(y1,…,yn),
где Qi — это или квантор всеобщности , или квантор существования $. По определению, ($xA(x))=(A(0)EA(1)), xA(x))=(A(0)A(1)). Задача выполнимости булевской формулы с кванторами (ЗВБФК) пребывает в ответе на вопрос о существовании комплекта значений переменных, на которых формула подлинна.
Нам необходимо выстроить сведение любого языка LZ из PSPACE к задаче ЗВБФК. Берем МТ для задачи Z и строим по ней игру, как это было продемонстрировано во второй части доказательства прошлой теоремы. После этого по данной игре строим МТ, контролирующую итог игры. Ходы игроков кодируем булевскими переменными. Тогда, к примеру, наличие выигрышной стратегии у белых задается условием
$w11$w12…$w1p(|I|)b11b12…b1p(|I|)f(I,w11,…).
Тут f(I,w11,…) — итог проверки истинности предиката. Эта проверка возможно представлена как вычисление по булевской схеме. Со своей стороны схеме конкретно сопоставляется булевская формула.
Так мы приобретаем квантифицированную булевскую формулу, которая подлинна тогда и лишь тогда, в то время, когда I лежит в LZ.
Теорема доказана.
Увидим, что при доказательстве теоремы 9.5 класс PSPACE возможно заменить на NPSPACE. Другими словами справедливо следующее утверждение.
Теорема 9.7. Задача Z лежит в классе NPSPACE тогда и лишь тогда, в то время, когда существует игра с полиномиальным от длины входа числом ходов и полиномиально вычислимым результатом такая, что LZ=Lw.
Первая часть доказательства теоремы 9.5.остается легко без трансформации. Для доказательства второй части увидим, что допускающая таблица для недетерминированной МТ будет иметь те же размеры, что и подобная таблица в теореме 9.5.
Следствие. PSPACE= NPSPACE.
Классы P и P/poly.
Разглядываем, как в большинстве случаев, задачи в форме распознавания. В начале курса мы говорили о возможности двух разных подходов к анализу понятия «сложность задачи». Один из них был связан с методом ответа задачи Z, второй – со сложностью СФЭ, реализующих булеву функцию fZ, значение которой дает ответ на задачу Z в форме распознавания.
Схема доказательства теоремы Кука позволяет без проблем установить соответствие между классами P и P/poly.
Вправду, для любой задачи из P возможно выстроить допускающую таблицу ее решения на машине Тьюринга так же, как это сделано выше при доказательстве теоремы Кука. По данной таблице мы выстроим КНФ полиномиальной длины f, а уже для данной КНФ — схему их функциональных элементов, вычисляющую f. Разумеется, что схема будет содержать полиномиальное число вершин. Так, справедливо следующее утверждение.
Теорема 9.1. P I P/poly.
А что будет, в случае, если Z P/poly? Выясняется, что класс P/poly шире класса P. Это связано с тем, что существуют алгоритмически неразрешимые неприятности. В курсе дискретной математики вам о них, возможно, говорили.
Приведем пример, что, по сути, есть известным со времен античности парадоксом брадобрея. В деревне имеется брадобрей, что бреет всех, кто не бреется сам. Попытайтесь ответить на вопрос, бреет ли он самого себя. При любом ответе получается несоответствие.
Облачим сейчас данный парадокс в «математическую форму». Неприятность остановки (halting problem) пребывает в том, дабы ответить на вопрос (мы о нем говорили выше, в то время, когда давали определение автомобили Тьюринга): остановится либо зациклится эта машина Тьюринга T на данном входе x? Оказывается, что, как и при брадобрея, любой ответ ведет к несоответствию. Другими словами не существует автомобили Тьюринга, которая решает проблему остановки.
Теорема. Неприятность остановки алгоритмически неразрешима.
Подтверждение. От противного. Пускай такая машина T* существует. Тогда на входе (T,x) она выдает ответ «да», в случае, если машина Т останавливается на этом входе, и «нет» в другом случае. (Тут Т – слово в алфавите А, являющееся описанием автомобили Т). Тогда по Т* возможно выстроить машину Тьюринга T’(x), которая , если T*(x,x)=”да”, начинает двигать головку в одну сторону и зацикливается, а при T*(x,x)=”нет” она останавливается. Что в этом случае будет означать T’(T’)? Остановится либо нет машина на этом входе? В случае, если «да», то это указывает, что T*(T’)= «нет», т.е. T’ не должна останавливаться на T’. В случае, если «нет», то это указывает, что T*(T’)= «да», т.е. T’ обязана останавливаться на T’.
Взяли несоответствие
Теорема доказана.
Разглядим функцию натурального довода f(n), принимающую значения 0 либо 1. Возможно продемонстрировать, что вычисление таковой функции возможно алгоритмически неразрешимой проблемой, т.е. не входит такая задача ни в какой класс сложности, а не только в класс P. Разглядим сейчас предикат Af(x)=f(|x|). Для любого фиксированного n предикат равен константе. А константе сопоставляется СФЭ, сложность которой также равна константе. Исходя из этого Af(x) P/poly, но его вычисление возможно алгоритмически неразрешимой проблемой.
Само собой разумеется, все это связано с тонкостями определений математических объектов и тем, что при вычислении предикатов главная сложность может лежать не в логических операциях, а в вычислении термов, от которых зависит предикат. Это вычисление связано с интерпретацией и допускает наличие в качестве довода предиката произвольной, сколь угодно сложновычислимой функции.
Результатом этого рассмотрения есть следующая несложная теорема (см. [6]).
Пускай задача Z в форме распознавания эквивалентна вычислению булевой функции f. Сущность в том, что с ростом числа переменных n=1,2,… мы имеем последовательность формул fn и схем Sn для данной функции. И конкретно свойства таковой последовательности для нас выжны.
Теорема. Функция (задача) f P тогда и лишь тогда, в то время, когда f P/poly и существует машина Тьюринга, которая за полиномиальное от длины входа n время сооружает СФЭ для fn.
Для доказательства увидим следующее. Теорема Кука дает конструктивный способ построения СФЭ полиномиального по входу размера за полиномиальное по входу время для функции f P. Т.е. в этом случае f P/poly и за полиномиальное от длины входа n время строястя СФЭ для fn.
И напротив, в случае, если f P/poly и существует Т — машина Тьюринга, которая для каждого отдельного n за полиномиальное от длины входа время по n сооружает СФЭ Sn для fn. Вычислений значения функции по данной схеме также потребует не более, чем полиномиального времени.
Грубо говоря, с точностью до «отличия в определениях» двух подходов: алгоритмического и схемного, возможно воображать себе классы P и P/poly достаточно родными. Про соотношение классов P и NP мы ничего не знаем. А вот на вопрос, как соотносится класс P/poly с классом всех СФЭ, ответ дает теорема Лупанова. Практически все схемы имеют экспоненциальную сложность 2n/n, т.е. множество функций (задач в форме распознавания), имеющих СФЭ полиномиального размера , пренебрежимо мало. Результат создал иллюзию безысходности в области изучений по алгоритмической сложности в 1960-е годы. На этом фоне итог Кука (1971 год) явился определенным идеологическим прорывом в том смысле, что он обратил внимание исследователей на небезнадежность решения задач, принадлежность которых к классу NPC не удалось доказать по окончании достаточно важных упрочнений квалифицированных экспертов. И не смотря на то, что таких задач было решено мало (пионером тут есть Л.Г.Хачиян , решивший за полиномиальное время задачу линейного программирования), но каждое из таких ответов явилось фундаментальным достижением в математике.
Кое-какие результаты
Обозначим через SPACE(f(n)) класс задач (языков), для которых существует МТ, трудящаяся на памяти с количеством, ограниченным f(n).
Подобно NSPACE(f(n)) класс задач (языков), для которых существует НМТ, трудящаяся на памяти с количеством, ограниченным f(n).
Приведем без доказательства следующее утверждение, уточняющее кое-какие из приведенных выше.
Теорема 9.7. NSPACE(f(n))ISPACE(f(n)2).