We consider three problems concerning change of bound variables (called by Alonzo Church "alpha conversion")

1. Given a formula F find an alpha convert of F with a smallest number of variables.
2. Given two alpha convertible formulas F and G find a shortest alpha conversion of F to G.
3. Given two alpha convertible formulas F and G find an alpha conversion of F to G which uses the smallest number of variables possible along the way.

We obtain the following results.

1. There is a polynomial time algorithm for solving problem (1). It is reducible to vertex coloring of chordal graphs.
2. Problem (2) is co−NP complete (in recognition form). The general feedback vertex set problem for digraphs is reducible to problem (2)
3. At most one variable besides those occurring in both F and G is necessary. This appears to be the folklore but the proof is not familiar.A polynomial time algorithm for the alpha conversion of F to G using at most one extra variable is given.