Published: August 29, 2008
Author(s)
Joan Boyar (University of Southern Denmark), Philip Matthews (University of Southern Denmark), Rene Peralta (NIST)
Conference
Name: 33rd International Symposium, MFCS 2008
Dates: 08/25/2008 - 08/29/2008
Location: Toru'n, Poland
Citation: Mathematical Foundations of Computer Science 2008, vol. 5162, pp. 168-179
We study the complexity of the Shortest Linear Program (SLP) problem, which is to the number of linear operations necessary to compute a set of linear forms. SLP is shown to be NP-hard. Furthermore, a special case of the corresponding decision problem is shown to be Max SNP-Complete. Algorithms producing cancellation-free straight-line programs, those in which there is never any cancellation of variables in GF(2) have been proposed for circuit minimization for various cryptographic applications. We show that such algorithms have approximation ratios of at least 3/2 and therefore cannot be expected to yield optimal solutions to non-trivial inputs.
We study the complexity of the Shortest Linear Program (SLP) problem, which is to the number of linear operations necessary to compute a set of linear forms. SLP is shown to be NP-hard. Furthermore, a special case of the corresponding decision problem is shown to be Max SNP-Complete. Algorithms...
See full abstract
We study the complexity of the Shortest Linear Program (SLP) problem, which is to the number of linear operations necessary to compute a set of linear forms. SLP is shown to be NP-hard. Furthermore, a special case of the corresponding decision problem is shown to be Max SNP-Complete. Algorithms producing cancellation-free straight-line programs, those in which there is never any cancellation of variables in GF(2) have been proposed for circuit minimization for various cryptographic applications. We show that such algorithms have approximation ratios of at least 3/2 and therefore cannot be expected to yield optimal solutions to non-trivial inputs.
Hide full abstract
Keywords
approximation ratio; circuit complexity; linear programs; MAX SNP-Complete; NP-HARD
Control Families
None selected
