Addition chain exponentiation problem is mentioned as a variant of problem 18.7 which is about transforming one string to another using BFS. Here we are supposed to compute the shortest addition chain exponentiation of x^n given the number n.
I could not come to any polynomial time solution to the problem and then found this wiki that says “problem of finding a shortest addition chain for a given set of exponents has been proven NP-complete”.
Can anyone confirm if they found a polynomial solution?
