Reduzierungen zwischen Sprachen unterschiedlicher Dichte?

Die Dichte einer Sprache ist eine Funktion d X : N → N, definiert als d X ( n ) = | { x ∈ X ∣ | x | ≤ n } | . Angenommen , A und B sind Sprachen über ein endliches Alphabet, A many-one logspace reduziert sich auf B und B nicht in L = DSPACE ( log n $X$$d_X \colon \mathbb{N} \to \mathbb{N}$

Wenn die Dichte von nicht polynomiell mit der Dichte von B zusammenhängt , kann es dann zu einer logarithmischen Reduzierung von B auf A kommen ?$A$$B$$B$$A$

Hintergrund

Ich erwarte, dass die Antwort nein ist, kann dies aber derzeit nicht anzeigen.

Klar, wenn in ist L , dann gibt es keine logspace Reduktion von B zu A . Es gibt also einige Beispiele, für die es möglich ist, eine eindeutige negative Antwort zu geben.$A$$\mathsf{L}$$B$$A$

I zuerst den Fall im Sinn hatte , wo einige harte Sprache ist, und A wird durch Einblasen von Löchern in erhaltenen B , indem man A = B ∩ G , für einige Spalt Sprache G , die alle Wörter der Länge enthält , n ∈ S G für einige Satz S G ⊆ N (siehe Schmidt 1985 und auch Regan und Vollmer 1997 ). Dies gewährleistet eine triviale Reduktion von A auf B . Lückensprachen G weisen üblicherweise exponentiell zunehmende Lücken zwischen den Größenintervallen in auf$B$$A$$B$$A = B\cap G$$G$$n \in S_G$$S_G \subseteq \mathbb{N}$$A$$B$$G$ . Dies stellt sicher, dass die Dichten von A und B nicht polynomiell zusammenhängen. Es gibt jedoch keine Garantie dafür, dass das Blasen von Löchern in einer Sprache immer zu einer Sprache führt, die zu wenig strukturiert ist, um das Ziel einer Reduktion von B zu sein . (Der Begriff "Blaslöcher"stammt vonDowney und Fortnow 2003.) Der Unterschied in der Dichte könnte ausreichen, um dies zu garantieren, aber ich verstehe nicht sofort, wie.$S_G$$A$$B$$B$

Ein anderes Beispiel ist, wenn eine Mischung aus einer harten Sprache und A ist . Erstellen Sie zunächst eine Gappy-Sprache A ∉ L, indem Sie eine Sprache C ∉ L mit einer Gap-Sprache G kreuzen . A enthält dann nur Instanzen von Größen, die in den Intervallen der Größenmenge S G liegen, die die Lückensprache bestimmen. Erstellen Sie nun B, indem Sie A mit einer harten Sprache D in den Lücken mischen , indem Sie die Vereinigung von A und den Schnittpunkt von D mit dem Komplement von G nehmen . Wenn $B$$A$$A\not\in\mathsf{L}$$C \not\in \textsf{L}$$G$$A$$S_G$$B$$A$$D$$A$$D$$G$$D$hart genug ist , um im Vergleich , wie D sind 2EXPSPACE -hard während C ∈ PSPACE ∖ L , dann durch die Raumhierarchie gibt kein Theorem logspace Reduktion von sein kann , D zu A . Es scheint dann möglich zu sein, dies zu erweitern, um zu zeigen, dass es keine Reduzierung des Protokollbereichs von B nach A gibt .$C$$D$$\textsf{2EXPSPACE}$$C \in \textsf{PSPACE} \setminus \textsf{L}$$D$$A$$B$$A$

Dies lässt immer noch die Situation, in der härter als C ist, aber "nicht zu viel", zum Beispiel D als SAT und C als STCON oder D als QBF-SAT und C als SAT. Um ein Ergebnis zu erhalten, muss man vielleicht L ≠ N P für STCON / SAT oder N P ≠ P S P A C E für SAT / QBF-SAT annehmen , aber es ist mir nicht sofort klar, wie man diese Annahmen verwendet.$D$$C$$D$$C$$D$$C$$\mathsf{L} \ne \mathsf{NP}$$\mathsf{NP} \ne \mathsf{PSPACE}$

Sei eine beliebige Sprache, die nicht in L ist , so dass A die Dichte 2 o ( n ) hat , und definiere B = { s ∘ 1 | s ∈ { 0 , 1 } ∗ } ∪ { s ∘ 0 | s ∈ A } . Hier ist ∘ Verkettung. Die Sprache B hat die Dichte Ω ( 2 n$A$ $L$$A$$2^{o(n)}$