Звідності. Відносна обчислюваність , Детальна інформація
Звідності. Відносна обчислюваність
Тип документу: Реферат
Сторінок: 11
Предмет: Математика
Автор: Олексій
Розмір: 75.5
Скачувань: 1164
Приклад 4. Існують множини А та В: А(В
Наприклад, візьмемо А=N та B=(.
Приклад 5. Існують множини А та В: А(В
Наприклад, візьмемо А=D та B=(.
Приклад 6. Не існують множини А та В: А(В
Згідно r13) А(т А(В, тому А(Т А(В. Отже, неможливо А(В
Приклад 7. Не існують множини А та В: А(В
Згідно r13) В(т А(В, тому неможливо А(В
Приклад 8. Покажемо, що А(В (T А(В.
Маємо х(А(В ( 2х(А(В ( 2х+1(А(В. Звідси отримуємо (А(В (х) = sg((А(В(2x)+(А(В(2x+1)). Отже, (А(В є (А(В-РФ.
Приклад 9. Покажемо, що А(В (T А(В.
Маємо х(А(В ( l(х)(А & r(х)(В ( 2l(х)(А(В & 2r(х)+1(А(В. Отже, (А(В (х) = (А(В(2l(х))((А(В(2r(х)+1). Отже, (А(В є (А(В-РФ.
.
є (D-РФ.
А-РПМ М T-повна, якщо L(T М .для кожної А-РПМ L
(x) визначене} є T-повною A-РПМ. Це негайно випливає з наступного твердження:
Тeорeма 4.1. Множина L є A-РПМ \xF0DB L(m DA.
(s(x))(, звiдки s(x)(DA. Отже, x(L \xF0DB s(x)(DA, тому L(m DA.
Нехай РФ f : L(m DA. Тодi x(L \xF0DB s(x)(DA. Але DA є A-РПМ, f є РФ, звiдки предикат "x(L" є A-ЧРП. Отже, L є A-РПМ
Наслідок 1. Якщо L є A-РПМ, то L(T DA.
Наслідок 2. A
Приклад 12. Із прикладу 11, зокрема, дістаємо: D є T-повною РПМ.
Ефективним варіантом теореми 9.4.1 є
(mDА для всiх А, z.
.
.
.
За наслiдком 2 теореми 9.4.1 маємо A(TDA для кожної A(N. Це означає, що при переходi вiд A до DA скачкоподiбно зростає складнiсть множини, тому DA називають скачком множини A.
Операцiю, яка кожнiй множинi A(N ставить у вiдповiднiсть множину DA, називають операцiєю скачка.
Теорема 4.3. A(T B \xF0DB DA(m DB.
Наприклад, візьмемо А=N та B=(.
Приклад 5. Існують множини А та В: А(В
Наприклад, візьмемо А=D та B=(.
Приклад 6. Не існують множини А та В: А(В
Згідно r13) А(т А(В, тому А(Т А(В. Отже, неможливо А(В
Приклад 7. Не існують множини А та В: А(В
Згідно r13) В(т А(В, тому неможливо А(В
Приклад 8. Покажемо, що А(В (T А(В.
Маємо х(А(В ( 2х(А(В ( 2х+1(А(В. Звідси отримуємо (А(В (х) = sg((А(В(2x)+(А(В(2x+1)). Отже, (А(В є (А(В-РФ.
Приклад 9. Покажемо, що А(В (T А(В.
Маємо х(А(В ( l(х)(А & r(х)(В ( 2l(х)(А(В & 2r(х)+1(А(В. Отже, (А(В (х) = (А(В(2l(х))((А(В(2r(х)+1). Отже, (А(В є (А(В-РФ.
.
є (D-РФ.
А-РПМ М T-повна, якщо L(T М .для кожної А-РПМ L
(x) визначене} є T-повною A-РПМ. Це негайно випливає з наступного твердження:
Тeорeма 4.1. Множина L є A-РПМ \xF0DB L(m DA.
(s(x))(, звiдки s(x)(DA. Отже, x(L \xF0DB s(x)(DA, тому L(m DA.
Нехай РФ f : L(m DA. Тодi x(L \xF0DB s(x)(DA. Але DA є A-РПМ, f є РФ, звiдки предикат "x(L" є A-ЧРП. Отже, L є A-РПМ
Наслідок 1. Якщо L є A-РПМ, то L(T DA.
Наслідок 2. A
Приклад 12. Із прикладу 11, зокрема, дістаємо: D є T-повною РПМ.
Ефективним варіантом теореми 9.4.1 є
(mDА для всiх А, z.
.
.
.
За наслiдком 2 теореми 9.4.1 маємо A(TDA для кожної A(N. Це означає, що при переходi вiд A до DA скачкоподiбно зростає складнiсть множини, тому DA називають скачком множини A.
Операцiю, яка кожнiй множинi A(N ставить у вiдповiднiсть множину DA, називають операцiєю скачка.
Теорема 4.3. A(T B \xF0DB DA(m DB.
The online video editor trusted by teams to make professional video in
minutes
© Referats, Inc · All rights reserved 2021