Varios variantes del problema de distancia de edición con eliminaciones de bloques son considerados. Se presentan algoritmos óptimos de tiempo polinómico para la distancia de edición con eliminaciones de bloques permitiendo inserciones de caracteres y movimientos de caracteres, pero sin movimientos de bloques. Mostramos que la distancia de edición con movimientos de bloques y eliminaciones de bloques es NP-completa (problemas de tiempo polinómico no deterministas en los que cualquier solución dada a dicho problema puede ser verificada en tiempo polinómico, y cualquier problema NP puede ser convertido en él en tiempo polinómico), y que puede ser reducido al problema de movimientos de bloques y eliminaciones de bloques no recursivos dentro de un factor constante.