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

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

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

мотивация

PARITY имеет верхнюю плотность . ДА (язык всех конечных двоичных строк) имеет верхнюю плотность 1. Любой конечный язык имеет верхнюю плотность 0. $1/2$
Разреженный язык обладает тем свойством, что существует такой многочлен , что для всех . Если - разреженный язык, то для многочлена степени один больше, чем у , поэтому верхняя плотность равна нулю. $L$ $p(n)$ $L_n - L_{n-1} \le p(n)$ $n$ $L$ $L_n \le p_1(n)$ $p_1$ $p$ $L$
Jin-Yi Cai и D. Sivakumar показали, что P-полный язык не может быть разреженным, если P = L (= LOGSPACE). Поскольку P = co-P, любой язык, в котором дополнение является разреженным, также не может быть P-полным, если только P = L.
По простому неравенству (см., Например, следствие 2 Россера и Шёнфельда, 1962 ) PRIMES имеет верхнюю плотность . Вопрос Известно ли, что проблемы PRIMES, FACTORING являются P-hard? обсуждает, является ли PRIMES P-hard (это, кажется, открыто в настоящее время). $(\log_2 e)/n$
В некотором смысле полные (или универсальные) языки для класса сложности содержат всю структуру класса. Поэтому моя предварительная гипотеза, основанная на дикой экстраполяции результатов Цая и Сивакумара, заключается в том, что такие языки не могут быть слишком редкими. Обычная полиномиальная граница, определяющая разреженные языки, кажется слишком ограничительной, поэтому я спрашиваю о границе, которая немного менее ограничительна.

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

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

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

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

cc.complexity-theory reference-request p-hardness Андраш Саламон
источник

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

2^{n} / n

$2^n/n$

Каве

Ответы:

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

Возьмите свой любимый P-полный язык . Этот язык имеет некоторую плотность . Теперь определим . В общем, будет некоторой функцией от , поэтому это может не определять для всех размеров, поскольку нас беспокоит только верхняя плотность, просто сделайте если . Какова верхняя плотность ? Ну у нас есть $L_n \subseteq \{0,1\}^n$ $d(n) \in \omega(1/n)$ $L'_{n + m} = \{x0^m | x \in L_n\}$ $m$ $n$ $L'$ $L'_k = \emptyset$ $k \neq n + m$ $L'$

d^{'} (n + m) = \frac{| L_{n + m}^{'} |}{2^{n + m}} = \frac{| L_{n} |}{2^{n + m}} \leq \frac{d (n)}{2^{m}}

$d'(n + m) = \frac{|L'_{n + m}|}{2^{n + m}} = \frac{|L_n|}{2^{n + m}} \leq \frac{d(n)}{2^m}$

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

Если мы хотим быть уверены, что мы меньше просто выберите , и тогда у нас будет . $1/n$ $m(n) = n$ $d'(2n) \leq d(n)/2^n \in O(1/n)$

Артем Казнатчеев
источник

Спасибо, это отвечает на вопрос. Этот аргумент, по-видимому, основан на полиномиальной связи с - будет ли достижима верхняя плотность ?

m

$m$

n

$n$

1 / \log n

$1/\log n$

Андрас Саламон

Я так думаю, вам просто нужно m = log log n. В общем случае для m = f (n) вы можете выбрать любое f, которое находится в LOG-пространстве (с n в одинарном). (или NC, если вы предпочитаете эти сокращения).

Артем Казнатчеев