Complexidade computacional de símbolos de contagem

Question

Considere a função de contagem $\{x\}^* ightarrow \mathbb N$ que conta o número de ocorrências do símbolo $x$.

Estou confuso sobre a complexidade (assintótica) de calcular esta função, onde a saída deve ser representada em um sistema não unário (por exemplo, binário).Minha intuição sugere fortemente que isso deve ser linear, ou seja, $O(n)$ onde $n$ é o número de ocorrências do símbolo $x$ na entrada.

No que me diz respeito, existem múltiplas interpretações de computação - por exemplo,

• máquinas de Turing de banda única, para as quais minha melhor ideia é tempo de execução $\Ômega(n^2\log n)$ Eu acho que o $\logn$ vem da suposição de que a função sucessora binária tem $\Ômega(n)$ tempo de execução, onde $n$ é o comprimento de uma representação binária de um número natural, e o $n^2$ vem da suposição de que a máquina de Turing tem que percorrer todos os $x$atingir sua contagem atual),
• máquinas de Turing multibanda, para as quais acho que tenho uma ideia do tempo de execução $\Ômega(n \log n)$,
• máquinas de acesso aleatório, que eu não conheço.

Então minha pergunta é a seguinte.

Qual é a complexidade computacional da função de contagem nos vários modelos de computação?É linear em algum deles?

Se for relevante, pergunto do ponto de vista da álgebra abstrata, onde estou tentando avaliar a complexidade computacional do problema verbal em algum grupo específico.

Answer 1

As máquinas de Turing são um bom modelo com diversas vantagens, principalmente a simplicidade, mas não são a primeira escolha na análise de algoritmos.Os algoritmos são normalmente analisados ​​implicitamente no modelo da máquina RAM e, em alguns casos, no modelo da máquina RAM. Modelo BSS.

Aqui estão alguns comentários sobre a complexidade computacional da contagem em vários modelos:

Máquina de Turing de fita única: Estes só são considerados porque é relativamente fácil provar limites inferiores para eles.Eles são um modelo de computação ainda menos realista do que as máquinas de Turing com múltiplas fitas.

Máquina de Turing multifita: É um exemplo padrão em complexidade amortizada que um contador crescente pode ser implementado usando $O(1)$ operações de bits amortizadas.Isso ocorre porque metade do tempo, apenas um bit muda, um quarto do tempo, apenas dois bits, e assim por diante, para um número total de bits alterados que é $1/2 + 2/4 + 3/8 + \cpontos = 2$.A complexidade da máquina de Turing é linear nisso e, portanto, a contagem pode ser implementada em $O(n)$.

Máquina RAM: Uma máquina RAM consiste em um número finito de registros e uma memória de acesso aleatório.Os registros são $O(\logn)$-bits de comprimento, onde $n$ é o tamanho da entrada.Operações razoáveis ​​em registradores levam tempo constante.Em particular, aumentando um contador que pode contar até $\mathit{poli}(n)$ leva $O(1)$ pior caso tempo.Em particular, sua função será executada em $O(n)$.

Máquina BSS: É preciso ter cuidado ao realizar operações aritméticas com números grandes.Na máquina RAM, a aritmética leva tempo constante apenas se a magnitude dos operandos for $\mathit{poli}(n)$.Uma máquina BSS permite acesso a registros especiais que armazenam valores em algum campo, digamos, os números reais.Você pode realizar comparações e aritmética em tempo constante, mas não funções como floor.Você também não tem permissão para usar esses valores para indexação.(Se você não se limitar o suficiente, em breve estará resolvendo SAT em tempo polinomial.) Você pode pensar em uma máquina BSS como uma máquina que acomoda operações de ponto flutuante, que na prática levam tempo constante, ignorando a precisão finita envolvida nelas. .