Issn 2072-0297 Молодой учёный Международный научный журнал Выходит еженедельно №3 (137) / 2017 р е д а к ц и о н н а я к о л л е г и я : Главный редактор
жүктеу/скачать 9,13 Mb. Pdf көрінісі
|
moluch 137 ch1
| x
∈ω дает набор чисел ( ) 1 , , x x n x t t … и ( ) n x -местную булеву функцию x β , зависящие от х такие, что ( ) ( ) ( ) ( ) 1 , , 1 x x x n x x A B t B t ∈ ⇔β … = Сводимости, промежуточные по силе между m-сводимостью и tt-сводимостью, называются табличными или сходимостями табличного типа. Имеется естественный путь получения таких сводимостей. Для этого надо зафиксировать замкнутый класс булевых функций и в определении tt-сводимости добавить слова функция из такого-то класса. Оказалось, что основных табличных сводимостей существует всего лишь семь: кроме m- и tt-, еще линейная, конъюнктивная, дизъюнктивная, позитивная и табличная с нормой 1 [4,11]. Поскольку класс { } 1 , , , , , , tt p c d l btt m оказался четко очерчен, удалось поставить и решить вопросы о различии элементарных теорий, классов вычислимо перечислимых полных множеств [1,2]. Сводимости по перечислимости отличаются от сводимостей по разрешимости тем, что информацию про множество А рано или поздно можно будет получить, но про А не обязательно. Говорят, что множество А е-сводится к В, если существует е-оператор Ф такой, что А=Ф(В). При этом е-оператор Ф переводит множество Х в ( ) ( ) ( ) { } ¦ : , & y Х x y x y W D X = ∃ ∈ ⊆ [2, 3, 5] Сводимости, промежуточные по силе между е- и m-, образуют класс сводимостей по перечислимости. Основными сводимостями по перечислимости являются { } , , , , , , , e s p c pc d pm m . В связи с тем, что вычислимо перечислимые множества образуют наименьшую e-степень, вопрос о полных множествах не стоит, зато с элементарными теориями удалось разобраться — они все попарно различаются [6–10]. Как уже отмечено, если e A B ≤ и имеется способ перечислять B, то по нему можно получить и эффективное перечисление А. Это позволяет, например, по множеству свойств В моделирующей системы перечислять свойства из А моделируемой системы, если для множеств этих свойств установлено е-сведение. Но если на самом деле a A ∉ , то перечисляя А, мы просто не получим элемент a , и вообще ни в какой момент времени нет оснований полагать, что a A ∉ . Этим отличаются сводимости по перечислимости. Приведем пример. Рассмотрим модель рюкзак . У нее входом X является пятерка , , , , R s v B K . Здесь R — некоторое конечное множество, , s v — функции, отображающие R в положительные целые числа Z + , выход { } 0,1 Y = . Система функционирует посредством функции ( ) ( ) ( ) ' 1, ' & & , , , , 0, x R x R K если R R R s x B v x K f R s v B K иначе ∈ ∈ ′ ∃ ⊆ ≤ ≥ = ′ ∑ ∑ Система жүктеу/скачать 9,13 Mb. Достарыңызбен бөлісу:
|