Табличная сводимость

tt- сводимост ь,- специальный вид алгоритмической сводимости. Пусть Аи В - два подмножества натурального ряда. Говорят, что Атаблично сводится к В (обозначение: [img: http://localhost:8080/file/052001-1.jpg] если существует алгоритм f, к-рый по всякому натуральному числу астроит булеву функцию [img: http://localhost:8080/file/052001-2.jpg] (функция задается, напр., своей таблицей, число аргументов функции может зависеть от а) и числа b1,..., b п такие, что принадлежность а к B эквивалентна истинности [img: http://localhost:8080/file/052001-3.jpg] Отношение [img: http://localhost:8080/file/052001-4.jpg] является предпорядком на множестве всех подмножеств натурального ряда, упорядочение по нему образует верхнюю полурешетку. Отношению [img: http://localhost:8080/file/052001-5.jpg] соответствует отношение эквивалентности [img: http://localhost:8080/file/052001-6.jpg] на подмножествах натурального ряда, а именно: [img: http://localhost:8080/file/052001-7.jpg] если [img: http://localhost:8080/file/052001-8.jpg] и [img: http://localhost:8080/file/052001-9.jpg] Классы эквивалентности по этому отношении) наз. табличными степенями (или tt -степенями). В теории алгоритмов рассматриваются также специальные виды Т. с., напр., ограниченная Т. с. (btt- сводимость), определяемая дополнительным требованием, чтобы число аргументов функции [img: http://localhost:8080/file/052001-10.jpg] не зависело от а. Если в качестве функции j берется просто функция x1, то сводимость наз. т-сводимостью (обозначение: [img: http://localhost:8080/file/052001-11.jpg] Сводимости, промежуточные между tt -сводимостью и т-сводимостью (т. е. такие алгоритмич. сводимости [img: http://localhost:8080/file/052001-12.jpg] что [img: http://localhost:8080/file/052001-13.jpg] [img: http://localhost:8080/file/052001-14.jpg] в частности все упомянутые выше, иногдааз. сводимостями табличного типа.