Плотность P-полных языков

10

Предположим, что - булев язык из конечных строк над . Пусть будет количеством строк в с длиной . Для функции от натуральных чисел до натуральных чисел имеет верхнюю плотность если для всех достаточно больших .{ 0 , 1 } L n L n d ( n ) L d ( n ) L n2 n d ( n ) nL{0,1}LnLnd(n)L d(n)Ln2nd(n)n

Есть ли P-полные булевы языки с более высокой плотностью ?O(1/n)

мотивация

  1. PARITY имеет верхнюю плотность . ДА (язык всех конечных двоичных строк) имеет верхнюю плотность 1. Любой конечный язык имеет верхнюю плотность 0.1/2

  2. Разреженный язык обладает тем свойством, что существует такой многочлен , что для всех . Если - разреженный язык, то для многочлена степени один больше, чем у , поэтому верхняя плотность равна нулю.p ( n ) L n - L n - 1p ( n ) n L L np 1 ( n ) p 1 p LLp(n)LnLn1p(n)nLLnp1(n)p1pL

  3. Jin-Yi Cai и D. Sivakumar показали, что P-полный язык не может быть разреженным, если P = L (= LOGSPACE). Поскольку P = co-P, любой язык, в котором дополнение является разреженным, также не может быть P-полным, если только P = L.

  4. По простому неравенству (см., Например, следствие 2 Россера и Шёнфельда, 1962 ) PRIMES имеет верхнюю плотность . Вопрос Известно ли, что проблемы PRIMES, FACTORING являются P-hard? обсуждает, является ли PRIMES P-hard (это, кажется, открыто в настоящее время).(log2e)/n

  5. В некотором смысле полные (или универсальные) языки для класса сложности содержат всю структуру класса. Поэтому моя предварительная гипотеза, основанная на дикой экстраполяции результатов Цая и Сивакумара, заключается в том, что такие языки не могут быть слишком редкими. Обычная полиномиальная граница, определяющая разреженные языки, кажется слишком ограничительной, поэтому я спрашиваю о границе, которая немного менее ограничительна.

Работа над lownness Фортнау, Хемаспандрой и другими также, возможно, связана.

Вопрос может быть задан для классов, отличных от P, но я не могу вспомнить какие-либо результаты, которые позволили бы установить плотность, скажем, -SAT. Указатели на соответствующую литературу приветствуются.k

Подтверждения

Смотрите также связанный вопрос Условная плотность простых чисел . Спасибо @Tsuyoshi Ito и @Kaveh за полезные комментарии к более ранней версии этого вопроса, которая, к сожалению, была некорректной.

Андраш Саламон
источник
Я думаю, что (или другая полиномиальная дробь) имеет слишком много строк, лучше спросить о верхних и нижних границах. 2n/n
Каве

Ответы:

6

Я не знаю, какова плотность общих P-полных задач, но вот дополнительный аргумент, который показывает, как снизить любую плотность ниже :1/n

Возьмите свой любимый P-полный язык . Этот язык имеет некоторую плотность . Теперь определим . В общем, будет некоторой функцией от , поэтому это может не определять для всех размеров, поскольку нас беспокоит только верхняя плотность, просто сделайте если . Какова верхняя плотность ? Ну у нас есть d ( n ) ω ( 1 / n ) L n + m = { x 0 m | x L n } m n L L k = k n + m L Ln{0,1}nd(n)ω(1/n)Ln+m={x0m|xLn}mnLLk=kn+mL

d(n+m)=|Ln+m|2n+m=|Ln|2n+md(n)2m

Теперь давайте используем LOG-сокращения для построения машины для используя машину для . Что ж, если вам дан ввод просто скопируйте его по одному на ленту запроса (также используйте счетчик, чтобы подсчитать, что такое ), затем используйте второй счетчик, чтобы сосчитать до , добавляя его каждый Когда вы добавляете ноль к ленте запросов (чтобы иметь пространство журнала, нам нужно и легко вычислимый). Затем запросите и верните результат в качестве ответа.MLMLxnm(n)m(n)poly(n)

Если мы хотим быть уверены, что мы меньше просто выберите , и тогда у нас будет .m ( n ) = n d ( 2 n ) d ( n ) / 2 nO ( 1 / n )1/nm(n)=nd(2n)d(n)/2nO(1/n)

Артем Казнатчеев
источник
Спасибо, это отвечает на вопрос. Этот аргумент, по-видимому, основан на полиномиальной связи с - будет ли достижима верхняя плотность ? n 1 / log nmn1/logn
Андрас Саламон
1
Я так думаю, вам просто нужно m = log log n. В общем случае для m = f (n) вы можете выбрать любое f, которое находится в LOG-пространстве (с n в одинарном). (или NC, если вы предпочитаете эти сокращения).
Артем Казнатчеев