Quali sono le conseguenze di Hash-Life in esecuzione in O (log n)?

Poiché Hashlife esegue il Gioco della vita che è completo di Turing, può eseguire qualsiasi programma computabile da Turing. Se la complessità per tutti i programmi eseguiti attraverso Hashlife verrebbe ridotta da log (n), che per esempio otterrà il (NP-complete) SAT (dove le implementazioni più note hanno O (2 ^ n)) si esegue in O (n). Forse con più simulazioni di Hashlife annidate l'una nell'altra, potresti forse risolvere ogni problema in O (log (n)). Ciò potrebbe alla fine portare a una prova per P = NP.

Il problema è che O (log (n)) funziona solo nel caso medio, mentre il caso peggiore ha ancora O (n). Hashlife ha tre principali ottimizzazioni:

1. A Quadtree per essere in grado di generalizzare le operazioni per tutti i nodi di livello superiore dell'albero
2. Canonicalizzazione di tutti i nodi in una tabella hash per avere un solo oggetto per ogni layout di nodo utilizzato
3. Memoria della prossima generazione per ogni nodo per evitare di ricalcolarlo

Entrambi questi ultimi funzionano egregiamente perché la maggior parte delle configurazioni ha molti modelli ricorrenti e relativamente pochi diversi nodi possibili. Per alcuni dei pattern di partenza più complessi, il simulatore di Golly inizia con la solita velocità in rapida crescita (quando il pattern è ancora piccolo e regolare), ma rallenta più il pattern cresce, quindi apparentemente non è una complessità puramente logaritmica. / p>

È possibile utilizzare memoisation per accelerare qualsiasi altra procedura deterministica ripetuta. È possibile utilizzare gli alberi per una gestione efficiente dei dati. Puoi utilizzare la canonicalizzazione per oggetti immutabili per risparmiare un sacco di memoria e calcoli.

What I meant to ask was if a certain algorithm could run faster, because it is executed in an environment that can run at O(log n). I've also updated my question to not imply a better time complexity, just running faster. I think your logic might be a little flawed.

Anche se HashLife è O (log n) e Turing Complete, non c'è alcuna garanzia che un programma che scrivi nel suo "linguaggio di programmazione" funzioni più velocemente. La possibilità più probabile è che esegua più lentamente, perché HashLife è ottimizzato per Conway's Game of Life, non per algoritmi di calcolo generici.

Modifica 2

Penso che guardare la matematica dietro grande O ti aiuterà. Non lo farò davvero qui.

Supponiamo di avere n celle nel gioco della vita. Ora implementiamo un algoritmo che cammina attraverso un elenco di m elementi. Questo algoritmo utilizza il tempo O (m). Quindi, con l'implementazione di ordinamento GoL, ciò avviene in O (n * m). Con l'implementazione più efficiente è necessario O (m * log (n)).

Modifica 1

algorithms that currently run in e.g. O(n), run in O(log n) instead?

Gli algoritmi non funzionano. Sono un modello. Implementazioni di algoritmi eseguiti.

Vorrei che la domanda venisse formulata in modo più chiaro.

Ecco i pensieri. Ci sono quattro casi: (senza GoL O (log n)) = > (con GoL O (log n))

1. algoritmi O (n) = > algoritmo O (log n)? Non possibile
2. implementazione O (n) = > algoritmo O (log n)? Può esistere
3. implementazione O (n) = > implementazione O (log n)? Esiste (GoL)
4. algoritmo O (n) = > implementazione O (log n)? Non possibile