Redukcje między językami o różnej gęstości?

Gęstość języka jest funkcją zdefiniowano jako Załóżmy, i są to języki na pewną skończoną alfabetu wielu jeden logspace redukuje się do , a jest w . Funkcje są wielomianowo powiązane, jeśli istnieją wielomiany i takie, że dla wszystkich , i $X$ $d_X \colon \mathbb{N} \to \mathbb{N}$

d_{X} (n) = | {x \in X ∣ | x | \leq n} | .

$d_X(n) = |\{x\in X \mid |x| \le n\}|.$

A

$A$

B

$B$

A

$A$

B

$B$

B

$B$

L = DSPACE (\log n)

$\textsf{L} = \text{DSPACE}(\log n)$

f, g : N \to N

$f,g \colon\mathbb{N} \to \mathbb{N}$

p

$p$

q

$q$

n \in N

$n\in \mathbb{N}$

f (n) \leq p (g (n))

$f(n) \le p(g(n))$

g (n) \leq q (f (n))

$g(n) \le q(f(n))$ .

Jeśli gęstość nie jest wielomianowo związana z gęstością , to czy może nastąpić zmniejszenie przestrzeni logicznej z do ? $A$ $B$ $B$ $A$

tło

Oczekuję, że odpowiedź brzmi „nie”, ale obecnie nie mogę tego pokazać.

Oczywiście, jeśli w , to nie ma obniżenie logspace z do . Jest więc kilka przykładów, dla których można podać jednoznaczną odpowiedź negatywną. $A$ $\mathsf{L}$ $B$ $A$

Najpierw miałem na myśli przypadek, w którym jest jakimś trudnym językiem, a jest uzyskiwane przez rozdmuchiwanie dziur w przez przyjęcie , dla jakiegoś języka przerwy który zawiera wszystkie słowa o długości dla pewnego zestawu (patrz Schmidt 1985 oraz Regan i Vollmer 1997 ). Gwarantuje to trywialne redukcji z do . Języki luk zwykle mają wykładniczo rosnące luki między przedziałami wielkości w . Zapewnia to, że gęstości i $B$ $A$ $B$ $A = B\cap G$ $G$ $n \in S_G$ $S_G \subseteq \mathbb{N}$ $A$ $B$ $G$ $S_G$ $A$ $B$ nie są powiązane wielomianowo. Jednakże, nie ma gwarancji, że dmuchanie dziury w języku zawsze prowadzi do języka, który ma zbyt małą strukturę być celem redukcji z . (Termin „ wydmuchiwanie dziur” pochodzi od Downey i Fortnow 2003. ) Różnica gęstości może być wystarczająca, aby to zagwarantować, ale nie od razu rozumiem, jak to zrobić. $B$

Innym przykładem jest, gdy jest mieszaniną twardej języka i . Najpierw utworzyć gappy język przez przecinające się trochę języka z językiem szczeliny . będzie wówczas zawierać tylko wystąpienia wielkości, które znajdują się w interwałach zestawu rozmiarów określających język odstępów. Teraz utwórz przez zmieszanie z jakiegoś twardego języka luki, poprzez unię i punkt przecięcia z dopełnieniem . Jeśli $B$ $A$ $A\not\in\mathsf{L}$ $C \not\in \textsf{L}$ $G$ $A$ $S_G$ $B$ $A$ $D$ $A$ $D$ $G$ $D$ jest wystarczająco trudny w porównaniu do , na przykład jest podczas gdy , to według twierdzenia o hierarchii przestrzeni nie można zmniejszyć przestrzeni logicznej z do . Następnie wydaje się możliwe, aby rozszerzyć to, aby pokazać, że nie ma redukcja logspace z do . $C$ $D$ $\textsf{2EXPSPACE}$ $C \in \textsf{PSPACE} \setminus \textsf{L}$ $D$ $A$ $B$ $A$

To wciąż pozostawia sytuację, w której jest trudniejsze niż ale „nie za dużo”, na przykład weźmy aby być SAT, a aby być STCON, lub aby być QBF-SAT, a aby być SAT. Aby uzyskać wynik, konieczne może być przyjęcie dla STCON / SAT lub dla SAT / QBF-SAT, ale nie od razu jest dla mnie jasne, jak wykorzystać te założenia. $D$ $C$ $D$ $C$ $D$ $C$ $\mathsf{L} \ne \mathsf{NP}$ $\mathsf{NP} \ne \mathsf{PSPACE}$

cc.complexity-theory reductions structural-complexity

— András Salamon
źródło

Co z

jest dowolnym językiem o gęstości

składa się ze wszystkich łańcuchów, których ostatni bit wynosi 0, zjednoczenie wszystkich łańcuchów, których ostatni bit wynosi 1, a pierwsze

bitów jest łańcuchem w A?

A

$A$

2^{o (n)}

$2^{o(n)}$

B

$B$

n - 1

$n-1$

— daniello

Myślę, że komentarz Daniello odpowiada na pytanie. Ogólnie rzecz biorąc, redukcje wielokrotne jeden mówią ci bardzo mało o gęstości, nawet jeśli redukcje wielokrotne jeden w obu kierunkach. Redukcje 1-1 i redukcje 1-1 w obu kierunkach (lub nawet silniejsze p-izomorfizmy) dają relacje między gęstością (tj. Hipoteza izomorfizmu Bermana-Hartmanisa motywująca twierdzenie Mahaneya; w rzeczywistości myślę, że izomorfizm BH mógł być główna motywacja do spojrzenia na gęstość w ogóle ...)

— Joshua Grochow

Niech będzie dowolnym językiem spoza , takim, że ma gęstość , i zdefiniuj Oto jest konkatenacja. Język ma gęstość $A$ $L$ $A$ $2^{o(n)}$

B = {s \circ 1 | s \in {0, 1}^{*}} \cup {s \circ 0 | s \in A} .

$B = \{s \circ 1 | s \in \{0,1\}^*\} \cup \{s \circ 0 | s \in A\}.$

\circ

$\circ$

B

$B$

Ω (2^{n})

$\Omega(2^n)$ , która jest wielobiegunowa w

. Z drugiej strony, przestrzeń logów

redukują się do siebie (od

poprzez połączenie

, a od

poprzez zmniejszenie wszystkich ciągów kończących się na

do najmniejszego tak wystąpienia A i usunięcie ostatniego bitu ze wszystkich ciągów kończące się na

). Stąd

, jak również.

2^{o (n)}

$2^{o(n)}$

A

$A$

B

$B$

A

$A$

B

$B$

0

$0$

B

$B$

A

$A$

1

$1$

0

$0$

B \notin L

$B \notin L$

— Daniello
źródło

Aby spełnić wymóg, że

powinien być wystarczająco twardy w tej konstrukcji. Wystarczy pozwolić, aby

był jedyną wersją Stopowania, która ma najwyżej jedną instancję każdego rozmiaru wejściowego.

B \notin L

$B \not\in \textsf{L}$

A

$A$

A

$A$

— András Salamon,

@ András Salamon, dziękuję za zwrócenie na to uwagi, zredagował odpowiedź, aby uchwycić komentarz.

— daniello