Pode uma codificação mais poderosa de uma entrada fazer um algoritmo que seja polinômio no número de entradas se torne exponencial?

Question

Esta é provavelmente uma pergunta muito básica, mas que estou tendo problemas para encontrar uma resposta definitiva para que esse tipo de coisa é desnatado na maioria dos cursos de algoritmos introdutórios. Tome um algoritmo como DFs que é executado no tempo polinômio no número de entradas. Neste caso, sua entrada é um gráfico com $ n $ vértices e $ m $ bordas e seu algoritmo corre no tempo $ O (m + n) $ .

Mas sabemos que, na realidade, devemos sempre considerar os comprimentos de codificações binárias ao calcular o tempo de execução. É por isso que algo como o algoritmo de programação dinâmica para a mochila não é realmente polinômio.

DFS leva em $ n + M $ "objetos" como entrada. Se dissermos que cada objeto leva um número fixo de bits (por exemplo, cada vértice leva 1 bit para codificar e cada borda leva 3 bits), então faz sentido para mim que o algoritmo é de fato polinomial na entrada. Mas há algum motivo que precisemos de um número fixo de bits para cada objeto? Pode existir uma codificação mais poderosa da entrada que leva $ \ log (m + n) $ bits, de repente, tornando o algoritmo exponencial?

Um pensamento que eu tinha era apenas que há uma suposição de que qualquer codificação prática no mundo real precisará de um número fixo de bits para cada "objeto" extra dado como entrada, se os objetos são vértices, letras em um string, etc.; Assim, é mais útil pensar em runtimes dessa maneira. Mas eu quero ter certeza de que acho que isso é fundamental para o meu entendimento. Obrigado antecipadamente!

Answer 1

Existem $ 2 ^ {n ^ 2} $ marcados marcados com gráficos direcionados na $ n $ vértices. Portanto, qualquer gráfico requer pelo menos $ n ^ 2 $ bits para representá-lo. Então, não há esperança de um esquema de codificação que sempre use no máximo $ O (\ Log n) $ bits e pode codificar todos os gráficos.

Se você quiser se concentrar em gráficos direcionados rotulados com $ n $ vértices e $ m $ bordas , há $ {n ^ 2 \ escolha m} $ deles, que para $ m \ ll n ^ 2 $ é aproximadamente $ (en ^ 2 / m) ^ m / \ sqrt {2 \ pi m} $ e, portanto, você precisará pelo menos < span class="contêiner matemática"> $ m \ lg (n ^ 2 / m) + O (m) $ bits para representar todos eles. Observe que isso é $ \ ômega (m) $ , então não há esperança para um esquema de codificação que usa apenas $ O (\ log m) $ bits (ou $ O (\ log (log (m + n)) $ bits) e pode representar todos esses gráficos. .

Claro, você pode considerar codificações que são logaritmicamente curtas, mas só podem expressar uma pequena fração de todos os gráficos possíveis. Sim, se você quisesse representar a entrada dessa maneira e resolver um problema de acessibilidade em tal gráfico, o DFS ordinário levaria tempo exponencial no tamanho da entrada.

Relacionado: você pode estar interessado em estruturas de dados sucintos .