Is binary encoding appropriate for the problem-language relationship?

It is proved that there exist encoding schemes which are arbitrarily as efficient as the binary encoding (in terms of compactness and arithmetic operations), with respect to which Khachiyan's algorithm for Linear Programming is exponential. This constitutes an objection to the standard translation of problems into languages via the binary encoding.

Authors

• Nimrod Megiddo

Keywords

No keywords are indexed for this paper.