Modelo de árvore de decisão

Em complexidade computacional e complexidade de comunicação o modelo de árvore de decisão é o modelo de computação ou comunicação no qual um algoritmo ou processo de comunicação é considerado basicamente uma árvore de decisão, ou seja, uma sequência de operações ramificadas baseadas em comparações de quantidades, sendo as comparações atribuidas uma unidade de custo computacional.

As operações ramificadas são chamadas de "testes" ou "pedidos". Nesta configuração, o algoritmo em questão pode ser visto como uma computação de uma Função Booleana $f:\{0,1\}^{n}\rightarrow \{0,1\}$ onde a entrada é uma série de pedidos e a saída é uma decisão final. Cada pedido é dependente de pedidos anteriores.

Várias variações de modelos de árvores de decisão podem ser utilizados dependendo da complexidade das operações permitidas na computação de uma única comparação e também pelo modelo de ramificação.

Modelos de árvore de decisão são instrumentos de estabelecimento do limite inferior para a complexidade computacional de certas classes de problemas computacionais e algoritmos: o limite inferior para análise de pior caso é proporcional a maior profundidade das árvores de decisão para todas as entradas possíveis de um certo problema computacional. A complexidade computacional de um problema ou um algoritmo em termos da árvore de decisão é chamado de complexidade da árvore de decisão ou complexidade do pedido'.

Classificação por complexidade de pedido computacional

Árvore de decisão simples

O modelo no qual toda decisão é baseada na comparação de dois números emum tempo constante é chamado simplesmente de modelo de árvore de decisão. Foi introduzido para estabelecer a complexidade computacional de Ordenação e busca.

A ilustração mais simples desta técnica de limite inferior é para o problema do menor número entre n números usando apenas comparações. Neste caso o modelo de árvore de decisão é uma árvore binária. Algoritmos para este problema de busca pode resultar em n saídas diferentes (porque qualquer um dos n números podem ser o menor). Sabe-se que a profundidade de uma árvore binária com n folhas é pelo menos $\log n$, o que nos dá um limite inferior de $\Omega (\log n)$ para o problema da busca. Porém este limite inferior é flexível, desde que o argumento seguinte mostre que pelo menos n - 1 comparações sejam necessárias: Antes que o menor número possa ser determinado, todo número exceto o menor deve "perder" (neste caso, ser maior na comparação) em pelo menos uma comparação.

Da mesa forma podemos provar o limite inferior $\Omega (n\log n)$ para ordenação. Neste caso, a existência de vários algoritmos de ordenação por comparação tendo esta complexidade de tempo, como o mergesort e o heapsort, mostram que o limite é pouco flexível.

Árvore de decisão linear

Árvores de decisão lineares, assim como as árvores de decisão simples, fazem uma decisão ramificada baseada em uma série de valores dados como entrada. Oposto à forma como árvores binárias funcionam, as árvores de decisão lineares têm três ramos de saída. A função linear $f(x_{1},\dots ,x_{i})$ é testada e as decisões ramificadas são feitas baseadas no sinal da funão (negativo, positivo ou 0).

Geometricamente, $f(x)$ define um hiperplano em Rⁿ. Uma série de valores de entrada que alcançam qualquer nó representa a interseção dos meio-planos definidos pelos nós.

Árvore de decisão algébrica

Árvores de decisão algébricas são uma generalização da árvore de decisão linear para permitir funções polinomiais de grau d. Geometricamente, o espaço é dividido em séries semi-algébricas (uma generalização do hiperplano). A avaliação da complexidade é mais difícil.

Classificação por modelo de computação de pedido

Árvore de decisão determinística

Se a saída de uma árvore de decisão é $f(x)$, para todo $x\in \{0,1\}^{n}$, então a árvore de decisão computa $f$. A profundidade de uma árvore é o número máximo de edidos que podem acontecer antes que uma folha seja alcançada e um resultado seja obtido. $D(f)$, a complexidade de $f$ na ávore de decisão determinística é a menor profundidade de todas as árvores de decisão determinísticas que computam $f$.

Árvore de decisão randomizada

Um meio de definir uma árvore de decisão randomizada é adicionando novos nós a uma árvore, cada um controlado por uma certa probabilidade $p_{i}$. Outra definição equivalente é selecionar uma árvore de decisão completa pelo começo dentre um conjunto de árvores de decisão baseando-se em uma distribuição de probabilidade. De acordo com essa segunda definição, a complexidade das árvores randomizadas é definida como a maior profundidade entre todas as árvores associadas à probabilidade maior que 0. $R_{2}(f)$ é definido como a complexidade da árvore de menor profundidade cujo resultado é $f(x)$ com probabilidade de pelo menos $2/3$ para todos os $x\in \{0,1\}^{n}$ (ou seja, com erro delimitado bilateralmente).

$R_{2}(f)$ é conhecido como complexidade de árvore de decisão randomizada de Monte Carlo, porque sue resultado pode ser errado de acordo com o erro limitado bilateralmente. A complexidade da árvore de Las Vegas $R_{0}(f)$ mede a profundidade esperada de uma certa árvore que deve ser correta (ou seja, contém zero erro). Também há a versão de erro unilateralmente delimitado conhecido como $R_{1}(f)$.

Árvore de Decisão não-determinística

A complexidade da árvore de decisão não-determinística é conhecida como complexidade de certificado (certificado é uma cadeia que certifica uma resposta à computação, ou a associação da cadeia a uma linguagem). Ela mede o número de bits de entrada que um algoritmo não-determinístico precisaria olhar para avaliar uma função com certeza.

Árvore de decisão quântica

A complexidade de uma árvore de decisão quântica $Q_{2}(f)$ é a profundidade da árvore quântica de menor profundidade que dá o resultado $f(x)$ com a probabilidade de pelo menos $2/3$ para todo $x\in \{0,1\}^{n}$. Outra quantidade, $Q_{E}(f)$, é definida como a profundidade da árvore de menor profundidade que dá o resultado $f(x)$ com probabilidade 1 em todos os casos (ou seja, computa $f$ exatamente. $Q_{2}(f)$ e $Q_{E}(f)$ são comumente conhecidas como complexidades de pedidos quânticos, porque a definição direta de uma árvore de decisão quântica é mais complicada do que o caso clássico. Da mesma forma que o caso randomizado, definimos $Q_{0}(f)$ e $Q_{1}(f)$.

Relação entre diferentes modelos

Segue imediatamente as definições de que todas as funções $f$ Booleanas de $n$-bits, $Q_{2}(f)\leq R_{2}(f)\leq R_{1}(f)\leq R_{0}(f)\leq D(f)\leq n$, e$Q_{2}(f)\leq Q_{E}(f)\leq D(f)\leq n$.

Blum and Impagliazzo, Hartmanis and Hemachandra, e Tardos descobriram que $D(f)\leq R_{0}(f)^{2}$. Noam Nisan descobriu que a árvore randomizada de Monte Carlo também é polinomialmente relacionada à complexidade da árvore de decisão determinística: $D(f)=O(R_{2}(f)^{3})$. (Nisan também mostrou que $D(f)=O(R_{1}(f)^{2})$.) Um corolário deste resultado é que $R_{0}(f)=O(R_{2}(f)^{3})$. Essa inequalidade pode ser flexível, porém; não há nenhum exemplo conhecido de uma separação super-linear entre $R_{0}(f)$ e$R_{2}(f)$.

A complexidade da árvore de decisão $Q_{2}(f)$ também é polinomialmente relacionada à $D(f)$. Midrijanis mostrou que $D(f)=O(Q_{E}(f)^{3})$, improving a quartic bound due to Beals et al. Beals et al. também mostrou que $D(f)=O(Q_{2}(f)^{6})$, e isto ainda é o melhor limite conhecido. Porém, a maior lacuna entre pedidos determinísticos e quânticos é apenas quadrático. Uma lacuna quadrática é atingida para o Algoritmo de Grover; $D(OR_{n})=n$ enquanto $Q_{2}(OR_{n})=\Theta ({\sqrt {n}})$.

É importante perceber que estas relacões polinomiais são válidas apenas para funções Booleanas totais. Para For funções booleanas parciais, que contêm um subconjunto de $\{0,1\}^{n}$, uma separação exponencial entre $Q_{E}(f)$ e $D(f)$ é possível; o primeiro exemplo de tal problema foi descoberto por Deutsch and Jozsa. O mesmo exemplo também dá uma separação exponencial entre $R_{2}(f)$ e $D(f)$.

Essas relações podem ser sumarizadas pelas seguintes inequalidades, das quais são verdadeiras até fatores constantes:

• $D(f)\leq R_{0}(f)^{2}$
• $D(f)\leq R_{1}(f)R_{2}(f)$
• $D(f)\leq R_{2}(f)^{3}$
• $R_{0}(f)\leq R_{2}(f)^{2}\log N$
• $D(f)\leq Q_{2}(f)^{6}$
• $D(f)\leq Q_{E}(f)^{2}Q_{2}(f)^{2}$
• $D(f)\leq Q_{1}(f)^{2}Q_{2}(f)^{2}$
• $R_{0}(f)\leq Q_{1}(f)Q_{2}(f)^{2}\log N$
• $D(f)\leq Q_{1}(f)Q_{2}(f)^{2}$

Ver também

• Árvore de decisão
• Modelo de computação
• Máquina abstrata