WikiDer > Ограниченная мера ресурсов

Ограниченная мера ресурсов Лутца является обобщением Мера Лебега к классы сложности. Первоначально он был разработан Джек Лутц. Подобно тому, как мера Лебега дает метод количественной оценки размера подмножеств Евклидово пространство ${ Displaystyle mathbb {R} ^ {п}}$мера с ограниченными ресурсами дает метод классификации размера подмножеств классов сложности.

Например, компьютерные ученые обычно считают, что класс сложности п (набор всех проблемы решения разрешимый в полиномиальное время) не соответствует классу сложности НП (множество всех задач решения, которые можно проверить, но не обязательно разрешить за полиномиальное время). Поскольку P является подмножество NP, это означало бы, что NP содержит больше проблем, чем P. Более сильная гипотеза, чем "P не NP"является утверждением" NP не имеет p-меры 0 ". Здесь p-мера является обобщением меры Лебега на подмножества класса сложности E, в котором содержится P. Известно, что P имеет p-меру 0, и поэтому гипотеза «NP не имеет p-меры 0» подразумевает не только то, что NP и P не равны, но и то, что NP находится в теоретико-мерный смысл "намного больше, чем P".

Определение

${ Displaystyle {0,1 } ^ { infty}}$ это набор всех бесконечный, двоичный последовательности. Мы можем просмотреть настоящий номер в единичный интервал как бесконечную двоичную последовательность, рассматривая ее двоичное расширение. Мы также можем просмотреть язык (набор двоичных струны) как бесконечную двоичную последовательность, задав пth кусочек последовательности к 1 тогда и только тогда, когда п-я двоичная строка (в лексикографический порядок) содержится в языке. Таким образом, наборы действительных чисел в единичном интервале и классы сложности (которые являются наборами языков) могут рассматриваться как наборы бесконечных двоичных последовательностей, и, таким образом, методы теория меры используется для измерения размера наборов действительных чисел, может применяться для измерения классов сложности. Однако, поскольку каждый вычислимый класс сложности содержит только счетный количество элементов (поскольку количество вычислимых языков счетно), каждый класс сложности имеет Мера Лебега 0. Таким образом, чтобы заниматься теорией меры внутри классов сложности, мы должны определить альтернативу мера это работает осмысленно на счетных наборах бесконечных последовательностей. Чтобы эта мера была значимой, она должна отражать что-то о базовом определении каждого класса сложности; а именно, что они определяются вычислительные проблемы которая может быть решена в пределах заданного ресурса.

В основе меры с ограниченными ресурсами лежит формулировка Вилле: мартингалы. А мартингейл это функция ${ displaystyle d: {0,1 } ^ {*} to [0, infty)}$ такой, что для всех конечных строк ш,

${ displaystyle d (w) = { frac {d (w0) + d (w1)} {2}}}$.

(Это первоначальное определение мартингала Вилле, позднее расширенное Джозеф Лео Дуб.) Мартингейл d говорят преуспевать в последовательности ${ Displaystyle S в {0,1 } ^ { infty}}$ если ${ Displaystyle limsup _ {п к infty} d (S upharpoonright п) = infty,}$ куда ${ displaystyle S upharpoonright n}$ это первый п кусочки S. Мартингейл преуспевает на множестве последовательностей ${ Displaystyle X substeq {0,1 } ^ { infty}}$ если он успешен в каждой последовательности в Икс.

Интуитивно мартингейл - это игрок, который начинает с некоторой конечной суммы денег (скажем, одного доллара). Он бесконечно читает последовательность битов. После прочтения конечного префикса ${ Displaystyle ш в {0,1 } ^ {*}}$, он ставит часть своих текущих денег на то, что следующий бит будет равен 0, а оставшуюся часть своих денег на то, что следующий бит будет равен 1. Он удваивает все деньги, которые были помещены на бит, который появляется следующим, и теряет деньги поместили на биту, которая не появилась. Он должен поставить все свои деньги, но он может «ничего не ставить», вкладывая половину своих денег на каждый бит. Для мартингейла d, d(ш) представляет собой сумму денег d после прочтения строки ш. Хотя определение мартингейла подразумевает, что мартингейл рассчитывает, сколько денег он будет иметь, а не рассчитывает, какие ставки делать, из-за ограниченного характера игры, знание значений d(ш), d(ш0), и d(ш1) достаточно для расчета ставок, которые d ставится на 0 и 1 после просмотра строки ш. Тот факт, что мартингейл - это функция, которая принимает в качестве входных данных строку, которую мы видели до сих пор, означает, что сделанные ставки являются исключительно функцией уже прочитанных битов; никакая другая информация не может повлиять на ставки (другая информация является так называемой фильтрация в обобщенная теория мартингалов).

Ключевым результатом в отношении меры к мартингалам является наблюдение Вилле о том, что множество ${ Displaystyle X substeq {0,1 } ^ { infty}}$ имеет меру Лебега 0 тогда и только тогда, когда существует мартингал, который преуспевает на Икс. Таким образом, мы можем определить набор меры 0 как такой, для которого существует мартингал, который действует на всех элементах набора.

Чтобы распространить этот тип меры на классы сложности, Лутц решил ограничить вычислительную мощность мартингала. Например, если вместо того, чтобы разрешить какой-либо мартингейл, мы потребуем, чтобы мартингейл был полиномиальное время вычислимы, то мы получаем определение p-меры: множество последовательностей имеет p-меру 0, если существует вычислимый за полиномиальное время мартингейл, успешный на съемочной площадке. Мы определяем множество как имеющее p-меру 1, если его дополнение имеет p-меру 0. Например, доказательство вышеупомянутой гипотезы о том, что NP не имеет p-меры 0, равносильно доказательству того, что ни один мартингал за полиномиальное время не преуспеет на все НП.

Почти готово

Проблема в том почти полный для класс сложности C, если он находится в C, и "многие" другие проблемы в C сводятся к нему. Более конкретно, подмножество проблем C, которые сводятся к проблеме, является набором меры один, в терминах меры, ограниченной ресурсами. Это более слабое требование, чем проблема полный для класса.

Рекомендации

• ван Мелкебек, Дитер (2001), Случайность и полнота вычислительной сложности, Спрингер, ISBN 3-540-41492-4, заархивировано из оригинал на 2011-07-19

внешняя ссылка

• Библиография с ограниченными ресурсами