In aptitude ci sono due algoritmi principali per la risoluzione delle dipendenze.

Il primo è un algoritmo che viene usato anche da programmi come apt-get e synaptic; verrà qui chiamato «risoluzione immediata». Viene invocato ogni volta che si seleziona in modo interattivo un pacchetto per l'installazione, e immediatamente dopo che uno o più pacchetti sono contrassegnati per l'installazione dalla riga di comando. La risoluzione immediata è veloce e risolve la maggior parte dei problemi di dipendenze, ma a volte non è in grado di trovare una soluzione.

Il secondo algoritmo, che verrà qui chiamato «risoluzione interattiva», viene invocato quando i pacchetti hanno dipendenze non soddisfatte anche dopo la risoluzione immediata^[11]. Può risolvere più dipendenze, permette di analizzare una soluzione prima di applicarla e permette di fornire feedback al risolutore, guidandolo verso una soluzione migliore.