Ресурсно-ограниченная мера
Ресурсно-ограниченная мера Лутца является обобщением меры Лебега на классы сложности . Первоначально он был разработан Джеком Лутцем . Точно так же, как мера Лебега дает метод количественной оценки размера подмножеств евклидова пространства. , мера, ограниченная ресурсами, дает метод классификации размера подмножеств классов сложности.
Например, ученые-компьютерщики обычно считают, что класс сложности P (набор всех проблем принятия решений, решаемых за полиномиальное время ) не равен классу сложности NP (набор всех проблем принятия решений, которые можно проверить, но не обязательно решить за полиномиальное время). . Поскольку P является подмножеством NP, это будет означать, что NP содержит больше проблем, чем P. Более сильной гипотезой, чем « P не является NP », является утверждение «NP не имеет p-меры 0». Здесь p-мера является обобщением меры Лебега на подмножества класса сложности E , в которых содержится P. Известно, что P имеет p-меру 0, поэтому гипотеза «NP не имеет p-меры 0» будет подразумевать не только то, что NP и P неравны, но и то, что NP в теоретико-мерном смысле «гораздо больше». чем П».
Определение
[ редактировать ]— множество всех бесконечных двоичных последовательностей . Мы можем рассматривать действительное число в единичном интервале как бесконечную двоичную последовательность, рассматривая его двоичное разложение . Мы также можем рассматривать язык (набор двоичных строк ) как бесконечную двоичную последовательность, установив n- й бит последовательности равным 1 тогда и только тогда, когда n -я двоичная строка (в лексикографическом порядке ) содержится в языке. Таким образом, наборы действительных чисел в единичном интервале и классы сложности (которые являются наборами языков) могут рассматриваться как наборы бесконечных двоичных последовательностей, и, таким образом, методы теории меры, используемые для измерения размера наборов действительных чисел, могут быть применяется для измерения классов сложности. Однако, поскольку каждый класс вычислимой сложности содержит только счетное число элементов (поскольку число вычислимых языков счетно), каждый класс сложности имеет меру Лебега 0. Таким образом, чтобы реализовать теорию меры внутри классов сложности, мы должны определить альтернативную меру это значимо работает на счетных множествах бесконечных последовательностей. Чтобы эта мера имела смысл, она должна что-то отражать базовое определение каждого класса сложности; а именно, что они определяются вычислительные задачи , которые можно решить в пределах заданного ресурса.
Вилле В основе меры, ограниченной ресурсами, лежит формулировка мартингалов . Мартингейл – это функция такой, что для всех конечных строк w ,
- .
(Это первоначальное определение мартингала, данное Вилле, позже расширенное Джозефом Лео Дубом мартингал d .) Говорят, что достигает успеха в последовательности если где это первые n битов S. — Мартингейл успешен на наборе последовательностей если он успешен в каждой последовательности в X .
Интуитивно понятно, что мартингейл — это игрок, который начинает с некоторой конечной суммы денег (скажем, одного доллара). Он считывает последовательность битов бесконечно. После прочтения конечного префикса , он ставит часть своих текущих денег на то, что следующий бит будет равен 0, а оставшуюся часть денег ставит на то, что следующий бит будет 1. Он удваивает сумму денег, вложенную в следующий бит, и теряет деньги. помещен на бит, который не появился. Он должен поставить все свои деньги, но он может «ничего не ставить», поставив половину своих денег на каждый бит. мартингала d Для d ( w ) представляет собой сумму денег, которую d имеет после прочтения строки w . Хотя в определении мартингейла мартингейл рассчитывает, сколько денег он будет иметь, а не рассчитывает, какие ставки сделать, из-за ограниченного характера игры необходимо знать значения d ( w ), d ( w 0) и d. ( w 1) достаточно для расчета ставок, которые d сделал на 0 и 1 после просмотра строки w . Тот факт, что мартингейл представляет собой функцию, которая принимает на вход уже увиденную строку, означает, что сделанные ставки являются исключительно функцией уже прочитанных битов; никакая другая информация не может повлиять на ставки (прочей информацией являются так называемые фильтрация в обобщенной теории мартингалов ).
Ключевым результатом, касающимся меры мартингалов, является наблюдение Вилле о том, что множество имеет меру Лебега 0 тогда и только тогда, когда существует мартингал, успешный на X . Таким образом, мы можем определить набор меры 0 как такой, для которого существует мартингал, который успешен на всех элементах набора.
Чтобы распространить этот тип меры на классы сложности, Лутц рассмотрел возможность ограничения вычислительной мощности мартингала. Например, если вместо того, чтобы допускать какой-либо мартингал, мы требуем, чтобы мартингал был вычислимым за полиномиальное время , тогда мы получаем определение p-меры: набор последовательностей имеет p-меру 0, если существует мартингал, вычислимый за полиномиальное время, который преуспевает на съемочной площадке. Мы определяем набор так, чтобы он имел p-меру 1, если его дополнение имеет p-меру 0. Например, доказательство вышеупомянутой гипотезы о том, что NP не имеет p-меры 0, равносильно доказательству того, что ни один мартингал с полиномиальным временем не увенчается успехом на весь НП.
Почти завершено
[ редактировать ]Задача почти завершена для класса сложности C, если она находится в C и к ней сводятся «многие» другие задачи из C. Более конкретно, подмножество проблем C, которые сводятся к проблеме, представляет собой набор меры с одной мерой в терминах меры ограниченности ресурсов. задачи Это более слабое требование, чем полнота для класса.
Ссылки
[ редактировать ]- ван Мелькебек, Дитер (2001), Случайность и полнота вычислительной сложности , Springer, ISBN 3-540-41492-4 , заархивировано из оригинала 19 июля 2011 г.