Reduzierungen zwischen Sprachen unterschiedlicher Dichte?

12

Die Dichte einer Sprache ist eine Funktion d X : NN, 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 )XdX:NN

dX(n)=|{xX|x|n}|.
ABABBL=DSPACE(logn). Funktionen sind polynomial bezogen , wenn Polynome p und q so daß für alle n N , f ( n ) p ( g ( n ) ) und g ( n ) q ( f ( n ) ) .f,g:NNpqnNf(n)p(g(n))g(n)q(f(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 ?ABBA


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.ALBA

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 GN (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 aufBABA=BGGnSGSGNABG . 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.SGABB

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 DBAALCLGASGBADADGDhart genug ist , um im Vergleich , wie D sind 2EXPSPACE -hard während C PSPACEL , 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 .CD2EXPSPACECPSPACELDABA

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 LN P für STCON / SAT oder N PP S P A C E für SAT / QBF-SAT annehmen , aber es ist mir nicht sofort klar, wie man diese Annahmen verwendet.DCDCDCLNPNPPSPACE

András Salamon
quelle
4
Was ist mit ? Eine Sprache der Dichte 2 o ( n ) und B besteht aus allen Zeichenfolgen, deren letztes Bit 0 ist. Vereinigen Sie alle Zeichenfolgen, deren letztes Bit 1 ist, und die ersten n - 1 Bits sind eine Zeichenfolge in A. A2o(n)Bn1
Daniello
2
Ich denke, Daniellos Kommentar beantwortet die Frage. Im Allgemeinen sagen viele Reduzierungen wenig über die Dichte aus, auch wenn Sie viele Reduzierungen in beide Richtungen haben. 1-1-Reduktionen und 1-1-Reduktionen in beide Richtungen (oder noch stärker p-Isomorphismen) geben Beziehungen zwischen der Dichte (nämlich die Berman-Hartmanis-Isomorphismus-Vermutung, die Mahaneys Theorem motiviert; ich denke, der BH-Isomorphismus könnte der gewesen sein Hauptmotivation für das Betrachten der Dichte überhaupt in erster Linie ...)
Joshua Grochow

Antworten:

8

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 LA2o(n)

B={s1|s{0,1}}{s0|sA}.
BΩ(2n), die in superpolynomial ist . Auf der anderen Seite verringern sich der A- und der B- Protokollbereich miteinander ( A bis B durch Verketten von 0 und B bis A durch Reduzieren aller Zeichenfolgen, die mit 1 enden, auf die kleinste Ja-Instanz von A und Entfernen des letzten Bits aus allen Zeichenfolgen endet mit 0 ). Daher B L als auch.2o(n)ABAB0BA10BL
daniello
quelle
Um die Anforderung zu erfüllen, dass , sollte A bei dieser Konstruktion ausreichend hart sein. Es reicht aus, A eine unäre Version von Halting zu lassen, die höchstens eine Instanz jeder Eingabegröße enthält. BLAA
András Salamon
@ András Salamon, danke für den Hinweis, hat die Antwort bearbeitet, um den Kommentar zu erfassen.
Daniello