A complexidade do tempo de um problema muda com a codificação do problema?

7

Suponha que eu tenha um problema de decisão e o codifique para um idioma . Agora, também posso codificá-lo para um idioma diferente . $D$ $L \subset \{0,1\}^*$ $L'$

Existe algum teorema relacionando a complexidade temporal de e ? $L$ $L'$

Como a complexidade temporal de um problema muda com codificações diferentes do mesmo problema?

complexity-theory terminology time-complexity user774025
fonte

11

Uma linguagem esparsa é uma linguagem em que o número de cadeias de comprimento é limitado por uma função polinomial de . Todos os idiomas unários são escassos. O teorema de Mahaney diz que, se uma linguagem esparsa é NP-completa, então P = NP.

n

$n$

n

$n$

Pål GD

8

Sim, a complexidade depende da codificação. A única coisa que você pode ter certeza é que, se estiver traduzindo da codificação $L$ para codificação $L'$ ou vice-versa tem a complexidade $f$ e $D$ pode ser resolvido com complexidade $g$ , então $D'$ (mesmo problema expresso com a codificação $L'$ ) pode ser resolvido com complexidade $O(f+g)$ indo e voltando entre codificações.

Não é apenas uma questão de tamanho da codificação. Para dar um exemplo simples, deixe $L$ ser inteiros positivos representados em binário e $L'$ ser inteiros positivos representados por sua fatoração primária. Existe um limite polinomial no tamanho de uma representação em termos da outra. No entanto, durante muito tempo, não se sabia se o teste de primalidade pode ser resolvido em tempo polinomial na representação binária; mas na representação de fatoração, é trivialmente polinomial (provavelmente $O(1)$ dependendo dos detalhes da representação).

Ou considere o problema de decisão "é inteiro $n$ um membro do conjunto $S$ ”. Se o conjunto é representado por uma lista não ordenada de números inteiros, esse problema evidentemente requer pelo menos tempo linear. Mas se o conjunto for representado por uma árvore de pesquisa equilibrada, o tempo de pesquisa será polilogarítmico no tamanho do conjunto.

Na maioria dos casos concretos, há uma representação evidente que todos assumem, ou mais precisamente, há uma classe de representações equivalentes a uma transformação que leva tempo insignificante. Mas, às vezes, a representação é relevante, mais frequentemente ao analisar estruturas de dados com mais precisão do que o tempo polinomial.

Gilles 'SO- parar de ser mau'
fonte

Eu gosto do seu ponteiro para estruturas de dados. O tempo de execução de muitos algoritmos gráficos depende criticamente da representação gráfica escolhida, que pode ser vista como codificação de entrada.

Raphael

6

A complexidade do tempo depende da codificação. As complexidades de tempo para $L$ e $L'$ arbitrariamente distantes, dada uma codificação bastante louca.

Na prática, geralmente nos preocupamos com a complexidade do tempo para uma codificação "natural". Freqüentemente, se houver várias codificações "naturais", todas elas tendem a levar aproximadamente à mesma complexidade de tempo (por exemplo, se você puder converter entre as codificações com eficiência). No entanto, não há garantia formal disso.

Portanto, tecnicamente falando, não se pode falar da complexidade temporal de um problema sem especificar a codificação específica usada.

DW
fonte

existe alguma definição rigorosa de "codificação natural"?

user774025

11

@ user774025, não. Exemplo: uma codificação natural de um número inteiro

x

$x$ é listar o número inteiro em formato binário. Uma codificação natural de uma lista

L = [x_{1}, x_{2}, \dots, x_{n}]

$L=[x_1,x_2,\dots,x_n]$ é a concatenação da codificação de

x_{1}

$x_1$ , a codificação de

x_{2}

$x_2$ , etc. (com delimitadores adequados). E assim por diante.

DW

@ user774025 Por outras palavras, não, não existe.

precisa saber é o seguinte

5

Considere qualquer idioma completo do NP $L$ e seu solucionador de força bruta (portanto, tempo exponencial) $A$ . Agora defina

$\qquad L' = \{ x\$0^{|x|^{|x|}} \mid x \in L \}$ .

Agora, claramente, uma leve adaptação de $A$ (use entrada somente até $\$$ ) decide $L'$ no tempo exponencial em $|x|$ e, portanto, no tempo polinomial no comprimento de sua própria entrada (que é de $L'$ ) Isso é, $L' \in \mathsf{P}$ .

Uma consideração mais simples é passar da codificação binária padrão para a codificação unária. De repente, verificações triviais de primalidade e até fatoração são executadas em tempo polinomial. Esse conceito está relacionado ao tempo de execução pseudo-polinomial .

Então, sim: a codificação importa se ela altera significativamente o comprimento da entrada . Portanto, a suposição típica é usar

uma codificação não unária com
no máximo, uma sobrecarga constante de fator (sobre a informação nua),

tão vago quanto isso.

Observe que nem mesmo os tempos de execução em termos de $\Theta$ -classes são invariantes usando apenas essa suposição. Imagine uma codificação de matrizes que intercale os números; isso adiciona um fator polinomial para encontrar o máximo. Portanto, você provavelmente deve ter cuidado, mesmo com codificações "boas", se quiser dizer algo com maior granularidade do que com fatores polinomiais.

Rafael
fonte

4

Não é exatamente uma resposta para sua pergunta, mas a conjectura de Berman-Hartmanis afirma (informalmente) que todos os problemas completos de NP são codificações um do outro, em algum sentido. A noção de codificação usada na conjectura preserva a complexidade do tempo, até uma diferença polinomial.

Yuval Filmus
fonte

"Não é exatamente uma resposta para sua pergunta" - é um comentário, então? ;)

Raphael

A complexidade do tempo de um problema muda com a codificação do problema?

Respostas: