Gęstość języków P-zupełnych

Załóżmy, że jest językiem boolowskim o skończonych łańcuchach ponad . Niech będzie liczbą łańcuchów w o długości . Dla funkcji od dodatnich liczb całkowitych do dodatnich liczb rzeczywistych, ma górną gęstość jeśli dla wszystkich wystarczająco dużych . $L$ $\{0,1\}$ $L_n$ $L$ $n$ $d(n)$ $L$ $d(n)$ $L_n \le 2^n d(n)$ $n$

Czy jakieś języki logiczne P-complete mają wyższą gęstość ? $O(1/n)$

Motywacja

PARITY ma górną gęstość . TAK (język wszystkich skończonych ciągów binarnych) ma górną gęstość 1. Każdy skończony język ma górną gęstość 0. $1/2$
Rzadki język ma właściwość, że istnieje wielomian taki że dla wszystkich . Jeśli jest językiem rzadkim, to dla wielomianu o jeden stopień większy niż , więc górna gęstość wynosi zero. $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 i D. Sivakumar wykazali, że język P-zupełny nie może być rzadki, chyba że P = L (= LOGSPACE). Ponieważ P = co-P, żaden język, którego dopełniacz jest rzadki, nie może być również P-zupełny, chyba że P = L.
Przez prostą nierówność (patrz np. Wniosek 2 Rossera i Schoenfelda 1962 ), PRIMES ma wyższą gęstość . Pytanie Czy problemy PRIMES, FACTORING są znane jako P-hard? dyskutuje, czy PRIMES jest twardy (wydaje się, że obecnie jest otwarty). $(\log_2 e)/n$
W pewnym sensie kompletne (lub uniwersalne) języki dla klasy złożoności zawierają całą strukturę klasy. Tak więc moja wstępna hipoteza, oparta na dzikiej ekstrapolacji wyniku Cai i Sivakumara, byłaby taka, że takie języki nie mogą być zbyt rzadkie. Zwykłe ograniczenie wielomianowe definiujące rzadkie języki wydaje się zbyt restrykcyjne, więc pytam o ograniczenie, które jest nieco mniej restrykcyjne.

Prace nad lowness przez Fortnow, Hemaspaandra i inni też prawdopodobnie związane.

Pytanie można zadać dla klas innych niż P, ale nie pamiętam żadnych wyników, które pozwoliłyby ustalić gęstość, powiedzmy, SAT. Wskazania na odpowiednią literaturę byłyby bardzo mile widziane. $k$

Podziękowanie

Zobacz także powiązane pytanie. Gęstość warunkowa liczb pierwszych . Dzięki @Tsuyoshi Ito i @Kaveh za pomocne komentarze do wcześniejszej wersji tego pytania, które niestety było źle postawione.

cc.complexity-theory reference-request p-hardness András Salamon
źródło

Myślę, że

(lub inny ułamek wielomianowy) ma zbyt wiele łańcuchów, lepszym pytaniem jest pytanie o górną i dolną granicę.

2^{n} / n

$2^n/n$

Kaveh

Odpowiedzi:

Nie wiem, jaka jest gęstość typowych problemów z kompletnym P, ale tutaj jest padding argument, który pokazuje, jak obniżyć dowolną gęstość poniżej : $1/n$

Wybierz swój ulubiony język P-complete . Ten język ma pewną gęstość . Teraz zdefiniuj . Ogólnie rzecz biorąc, będzie jakąś funkcją , więc może nie definiować $L_n \subseteq \{0,1\}^n$ $d(n) \in \omega(1/n)$ $L'_{n + m} = \{x0^m | x \in L_n\}$ $m$ $n$ $L'$ dla wszystkich rozmiarów, ponieważ martwimy się tylko o górną gęstość, po prostu ustaw jeśli . Jaka jest górna gęstość ? Cóż, mamy $L'_k = \emptyset$ $k \neq n + m$ $L'$

{re}^{'} (n + m) = \frac{| {L.}_{n + m}^{'} |}{{2)}^{n + m}} = \frac{| {L.}_{n} |}{{2)}^{n + m}} \leq \frac{re (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}$

Teraz możemy użyć redukcji LOG do zbudowania maszyny dla za pomocą maszyny dla . Cóż, jeśli otrzymałeś wejście po prostu skopiuj je po kolei na taśmę zapytania (użyj także licznika, aby policzyć, co to jest ), a następnie użyj drugiego licznika, aby policzyć do , dodając jeden co kiedy dodasz zero do taśmy zapytania (aby mieć miejsce w dzienniku, potrzebujemy i łatwo obliczalnego). Następnie prześlij zapytanie i zwróć wynik jako odpowiedź. $M$ $L$ $M'$ $L'$ $x$ $n$ $m(n)$ $m(n) \in poly(n)$

Jeśli chcemy mieć pewność, że jesteśmy mniejsi niż po prostu wybierzmy , a następnie otrzymamy . $1/n$ $m(n) = n$ $d'(2n) \leq d(n)/2^n \in O(1/n)$

Artem Kaznatcheev
źródło

Dzięki, to odpowiada na pytanie. Ten argument wydaje się polegać na tym, że

jest wielomianowo powiązany z

- czy można osiągnąć wyższą gęstość

m

$m$

n

$n$

1 / \log n

$1/\log n$

András Salamon,

Myślę, że tak, po prostu potrzebujesz m = log log n. Ogólnie dla m = f (n) możesz wybrać dowolne f, które znajduje się w przestrzeni LOG (z nw unarnym). (lub NC, jeśli wolisz te redukcje).

Artem Kaznatcheev