Exponenciais duplos vs exponenciais únicos

Aqui estão quatro princípios que não consigo conciliar:

Algoritmos de tempo exponencial duplo são executados no tempo com constante $O(2^{2^{n^k}})$ $k \in \mathbb{N}$
Algoritmos de tempo exponencial são executados em com constante $O(2^{n^k})$ $k \in \mathbb{N}$
O primeiro limite cresce estritamente mais rápido que o último; ou seja, existem algoritmos que são executados em tempo exponencial duplo, mas não em tempo exponencial
Aplicando ao duplo limite exponencial, temos , que se enquadra no limite exponencial declarado anteriormente $a^{b^c} = a^{bc}$ $O(2^{2^{n^k}}) = O(2^{2^{nk}}) = O(2^{2nk})$

Sinto falta de alguma sutileza relacionada à definição de um algoritmo de tempo exponencial como sendo executado em vez de , mas não estou com certeza exatamente onde está a sutileza. $O(2^{\mathrm{poly}(n)})$ $O(2^{n})$

asymptotics discrete-mathematics notation badroit
fonte

Editei as tags e o tile desde que, realmente, essa pergunta não tem nada a ver com a teoria da complexidade: trata-se de notação matemática e do comportamento assintótico de funções matemáticas.

David Richerby

Respostas:

A questão se resume a terminologia ambígua.

$(a^b)^c = a^{bc}$ , mas . Em outras palavras, os expoentes não são associativos. $a^{(b^c)} \neq a^{bc}$

Convencionalmente, exponenciais aninhados sem parênteses são agrupados dessa segunda maneira, porque é mais útil. Então . Se quiséssemos falar sobre , poderíamos escrever , então reservamos a notação exponencial dupla para o outro caso. $2^{2^n} = 2^{(2^n)} \neq 2^{2n}$ $(2^2)^n$ $2^{2n}$

Draconis
fonte

Essa convenção é a única sensata. Como você descreveu, escolher a outra maneira de agrupar seria inútil, pois já poderíamos expressar esse valor / função usando vez de um "duplo exponencial" sofisticado.

a^{b \cdot c}

$a^{b\cdot c}$

Bakuriu

@ Bakuriu Oh, de fato, embora seja importante notar que é apenas uma convenção. (Não poderia ser também a convenção sempre usar parênteses, que é o LaTeX faz: ele se recusa a imaginar como grupo a^b^c, e gera um erro em vez disso.)

Draconis

Toda notação é "apenas uma convenção". Descrever " " como "apenas uma convenção" sugere que existem outras alternativas plausíveis, mas, na verdade, não existem.

a^{b^{c}} = a^{(b^{c})}

$a^{b^c}=a^{(b^c)}$

David Richerby

@DavidRicherby Certamente, toda notação é convencional! Mas isso não significa que não vale a pena notar. É uma escolha deliberada dos matemáticos usar essa notação: e é uma boa escolha, porque elimina a ambiguidade e é mais útil que a alternativa. Mas ainda é uma escolha, e nada impede que você a defina de maneira diferente (além de confundir os leitores sem nenhum ganho real).

Draconis 21/07

@Bakuriu Eu não chegaria ao ponto de dizer que é a única convenção sensata, porque me parece muito sensato supor que todas as operações são avaliadas da esquerda para a direita, a menos que haja parênteses. É o que fazemos com adição e subtração e o que as crianças aprendem na escola com o "PEMDAS". O fato de a exponenciação não seguir a convenção me tropeçou no passado, e quase todo mundo que aprende sobre ela.

6005

$a^{(b^c)}$ não é o mesmo que . Quando as pessoas escrevem , geralmente significam , não . $(a^b)^c$ $2^{2^k}$ $2^{(2^k)}$ $(2^2)^k$

DW
fonte