Este é um seguimento da resposta de Suresh. Como ele diz, existem muitos problemas de construção na geometria computacional em que a complexidade da saída é um limite inferior trivial no tempo de execução de qualquer algoritmo. Por exemplo: arranjos de linhas planas, diagramas tridimensionais de Voronoi e gráficos de visibilidade planar têm complexidade combinatória no pior caso, portanto, qualquer algoritmo que construa esses objetos trivialmente requer Ω ( n 2 ) tempo no pior caso . (Existem algoritmos de tempo O ( n 2 ) para todos os três desses problemas.)Θ( n2)Ω ( n2)O ( n2)
Mas restrições semelhantes são conjecturadas para se aplicarem também a problemas de decisão . Por exemplo, dado um conjunto de n linhas no plano, com que facilidade você pode verificar se três linhas passam por um ponto comum? Bem, você pode construir o arranjo das linhas (o gráfico planar definido por seus pontos de interseção e os segmentos entre eles), mas isso leva . Um dos principais resultados da minha tese de doutorado foi que, dentro de um modelo de árvore de decisão restrita, mas natural de computação, Ω ( n 2 ) tempo é necessário para detectar cruzamentos triplos. Intuitivamente, devemos enumerar tudo (Θ ( n2)Ω ( n2) pontos de interseção e procure duplicatas.( n2)
Da mesma forma, há um conjunto de números em que triplos de elementos somam zero. Portanto, qualquer algoritmo (modelado por uma determinada classe de árvores de decisão) para testar se um determinado conjunto contém três elementos que somam zero requer Ω ( n 2 ) tempo . (É possível cortar alguns logs via paralelismo no nível de bits, mas tanto faz.)Θ ( n2)Ω ( n2)
Outro exemplo, também da minha tese, é o problema de Hopcroft: dados pontos e n linhas no plano, qualquer ponto contém alguma linha. O número de pior caso de incidência de linha de ponto é conhecido por ser Θ ( n 4 / 3 ) . I provou que em um modelo restringido (mas ainda natural) de computação, Ω ( n 4 / 3 ) é necessário tempo para determinar se existe ainda uma incidência de linha de ponto. Intuitivamente, devemos enumerar todos Θ ( n 4 / 3 ) pertonnΘ ( n4 / 3)Ω ( n4 / 3)Θ ( n4 / 3) -incidências e verifique cada uma para ver se é realmente uma incidência.
Formalmente, esses limites inferiores ainda são apenas conjecturas, porque exigem modelos de computação restritos, especializados no problema em questão, especialmente no problema de Hopcroft. No entanto, provar limites mais baixos para esses problemas no modelo de RAM provavelmente é tão difícil quanto qualquer outro problema de limite inferior (ou seja, não temos idéia) - veja o artigo da SODA 2010 de Patrascu e Williams relacionando generalizações do 3SUM ao tempo exponencial hipótese.