Reversible Turing Machines and Polynomial Time Reversibly Computable Functions
Giuseppe Jacopini, Patrizia Mentrasti, Giovanna Sontacchi · SIAM Journal on Discrete Mathematics · 1990
The reversible Turing machine (i.e., r-machine) was introduced initially by C. H. Bennett [IBM J. Res. Develop., 6 (1973), pp. 525–532]. In the first part of the paper a convenient representation of r-machines is introduced by means of diagrams. By using this method the following theorem can be proved: the invertible partial functions are exactly those that can be computed without surplus information by r-machines. Therefore the following problem is pointed out: are the invertible functions that can be computed in polynomial time also r-computable in polynomial time? In the second part of the work this open question is connected with the problem P = NP and with the problem of the existence of “one-way” bijections.