Set Theory and Logic


One-Wayness in Input-Saving Turing Machine

Authors: Alexandre de Castro

In computer science, the P =?NP is to determine whether every language accepted by some nondeterministic algorithm in polynomial-time is also accepted by some deterministic algorithm in polynomial-time. Currently, such a complexity-class problem is proving the existence of one-way functions: functions that are computationally ‘easy’, while their inverses are computationally ‘hard’. In this paper, I show that this outstanding issue can be resolved by an appeal to physics proofs about the thermodynamic cost of computation. The physics proof presented here involves Bennett's reversible algorithm, an input-saving Turing machine used to reconcile Szilárd's one-molecule engine (a variant of Maxwell’s demon gedankenexperiment) and Landauer’s principle, which asserts a minimal thermodynamic cost to performing logical operations, and which can be derived solely on the basis of the properties of the logical operation itself. In what follows, I will prove that running the Bennett's algorithm in reverse leads to a physical impossibility and that this demonstrates the existence of a non-invertible function in polynomial-time, which would otherwise be invertible.

Comments: 10 Pages.

Download: PDF

Submission history

[v1] 2014-03-08 19:48:17

Unique-IP document downloads: 9 times

Add your own feedback and questions here:
You are equally welcome to be positive or negative about any paper but please be polite. If you are being critical you must mention at least one specific error, otherwise your comment will be deleted as unhelpful.

comments powered by Disqus