Reduções entre idiomas de diferentes densidades?

12

A densidade de uma linguagem é uma função definida como Suponha que e são linguagens mais algum alfabeto finito, muitos e um logspace reduz a e não está na . Funções são polinomialmente relacionada se existem polinómios e tais que, para todos os , ed X : NN d X ( n ) = | { X X | | x | n } | . A B A B B L = DSPACE ( log n ) f , g : NNXdX:NN

dX(n)=|{xX|x|n}|.
ABABBL=DSPACE(logn)f,g:NNq n N f ( n ) p ( g ( n ) ) g ( n ) q ( f ( n ) )pqnNf(n)p(g(n))g(n)q(f(n)) .

Se a densidade de não estiver polinomialmente relacionada à densidade de , pode haver uma redução do espaço de log de para ?B B AABBA


fundo

Espero que a resposta seja não, mas atualmente não posso mostrar isso.

Claramente, se é de , então não há redução logspace de para . Portanto, existem alguns exemplos para os quais é possível fornecer uma resposta negativa definitiva.L B AALBA

Primeiro, eu tinha em mente o caso em que é uma linguagem difícil, e é obtido fazendo buracos em , tomando , para alguma linguagem que contém todas as palavras de comprimento para algum conjunto (veja Schmidt 1985 e também Regan e Vollmer 1997 ). Isto garante uma redução trivial de para . Linguagens de intervalo geralmente têm intervalos exponencialmente crescentes entre os intervalos de tamanhos em . Isso garante que as densidades de eBB A = B L L n S G S GN A B G S L A B BABA=BGGnSGSGNABGSGAB não são polinomialmente relacionados. No entanto, não há garantia de que abrindo buracos em uma linguagem sempre dá origem a uma linguagem que tem muito pouca estrutura para ser alvo de uma redução de . (O termo soprando orifícios é de Downey e Fortnow 2003 ). A diferença de densidades pode ser suficiente para garantir isso, mas não vejo imediatamente como.B

Outro exemplo é quando é uma mistura de uma linguagem de disco e . Primeiro cria uma linguagem gappy por intersecta alguma linguagem com uma linguagem de lacuna . conterá apenas instâncias de tamanhos que estão nos intervalos do conjunto de tamanhos determinando o idioma do intervalo. Agora crie misturando com alguma língua difícil as lacunas, tomando a união de e da interseção de com o complemento do . SeA A L C L G A S G B A D A D G D C D 2EXPSPACE C PSPACEL D A B ABAALCLGASGBADADGDé difícil o suficiente em comparação com , como sendo -hard enquanto , então pelo teorema da hierarquia de espaço não pode haver redução do espaço de log de para . Em seguida, parece possível estender esta para mostrar que não há redução logspace de para .CD2EXPSPACECPSPACELDABA

Isso ainda deixa a situação em que é mais difícil que mas "não é demais", por exemplo, considere como SAT e como STCON ou como QBF-SAT e como SAT. Para obter um resultado, pode ser necessário assumir para STCON / SAT ou para SAT / QBF-SAT, mas não é imediatamente claro para mim como usar essas suposições.DCDCDCLNPNPPSPACE

András Salamon
fonte
4
E quanto a qualquer linguagem de densidade e consiste em todas as strings cujo último bit é 0, une todas as strings cujo último bit é 1 e os primeiros bits são uma string em A? A2o(n)Bn1
Daniello
2
Acho que o comentário de daniello responde à pergunta. Em geral, muitas reduções de uma falam muito pouco sobre densidade, mesmo que você tenha reduções de uma em ambas as direções. Reduções de 1-1 e reduções de 1-1 em ambas as direções (ou ainda mais fortes, p-isomorfismos) dão relações entre densidade (a saber, a conjectura de isomorfismo de Berman-Hartmanis motivando o teorema de Mahaney; de fato, acho que o isomorfismo de BH pode ter sido o principal motivação para olhar para a densidade em tudo, em primeiro lugar ...)
Joshua Grochow

Respostas:

8

Seja qualquer idioma que não esteja em , de modo que tenha densidade , e defina Aqui é concatenação. O idioma possui densidade , que é superpolinomial em . Por outro lado, o espaço de log e reduz um ao outro ( a concatenando e a reduzindo todas as seqüências que terminam emL A 2 o ( n ) B = { s 1 | s { 0 , 1 } } { s 0 | s A } . B Ω ( 2 n ) 2 o ( n ) A B A B 0 B A 1 0 B LA LA2o(n)

B={s1|s{0,1}}{s0|sA}.
BΩ(2n)2o(n)ABAB0BA1para a menor instância yes de A e removendo o último bit de todas as strings que terminam em ). Daí bem.0BL
daniello
fonte
Para satisfazer o requisito de que , deve ser suficientemente difícil nessa construção. É suficiente permitir que seja uma versão unária do Halting, que possui no máximo uma instância de cada tamanho de entrada. A ABLAA
András Salamon
@ András Salamon, obrigado por apontar isso, editou a resposta para capturar o comentário.
Daniello