Skip to main content
U.S. flag

An official website of the United States government

Official websites use .gov
A .gov website belongs to an official government organization in the United States.

Secure .gov websites use HTTPS
A lock ( ) or https:// means you’ve safely connected to the .gov website. Share sensitive information only on official, secure websites.

On the shortest linear straight-line program for computing linear forms

Published

Author(s)

Joan Boyar, Philip Matthews, Rene Peralta

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.
Proceedings Title
Mathematical Foundations of Computer Science 2008 (Lecture Notes in Computer Science)
Volume
5162
Conference Dates
August 25-29, 2008
Conference Location
Torun, PL
Conference Title
33rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2008)

Keywords

approximation ratio, circuit complexity, linear programs, NP-HARD, MAX SNP-Complete

Citation

Boyar, J. , Matthews, P. and Peralta, R. (2008), On the shortest linear straight-line program for computing linear forms, Mathematical Foundations of Computer Science 2008 (Lecture Notes in Computer Science), Torun, PL, [online], https://doi.org/10.1007/978-3-540-85238-4_13 (Accessed November 10, 2024)

Issues

If you have any questions about this publication or are having problems accessing it, please contact reflib@nist.gov.

Created August 28, 2008, Updated October 12, 2021