Reduções entre idiomas de diferentes densidades?

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 , e $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))$ .

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

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. $A$ $\mathsf{L}$ $B$ $A$

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 e $B$ $A$ $B$ $A = B\cap G$ $G$ $n \in S_G$ $S_G \subseteq \mathbb{N}$ $A$ $B$ $G$ $S_G$ $A$ $B$ 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 . Se $B$ $A$ $A\not\in\mathsf{L}$ $C \not\in \textsf{L}$ $G$ $A$ $S_G$ $B$ $A$ $D$ $A$ $D$ $G$ $D$ é 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 . $C$ $D$ $\textsf{2EXPSPACE}$ $C \in \textsf{PSPACE} \setminus \textsf{L}$ $D$ $A$ $B$ $A$

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. $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
fonte

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?

A

$A$

2^{o (n)}

$2^{o(n)}$

B

$B$

n - 1

$n-1$

Daniello

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

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 em $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)$

2^{o (n)}

$2^{o(n)}$

A

$A$

B

$B$

A

$A$

B

$B$

0

$0$

B

$B$

A

$A$

1

$1$ para a menor instância yes de A e removendo o último bit de todas as strings que terminam em ). Daí bem.

0

$0$

B \notin L

$B \notin L$

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.

B \notin L

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

A

$A$

A

$A$

András Salamon

@ András Salamon, obrigado por apontar isso, editou a resposta para capturar o comentário.

Daniello

Reduções entre idiomas de diferentes densidades?

fundo

Respostas: