Before revision:  All previous algorithms proposed for this problem have doubly exponential complexity (and this is so for almost all input data) .
After revision:  All previous algorithms proposed for this problem have doubly exponential complexity .