On the Shortest Linear Straight-Line Program for Computing Linear Forms
On the Shortest Linear Straight-Line Program for Computing Linear Forms
复制标题
DOI：
10.1007/978-3-540-85238-4_13
复制
发表时间：
2008-08
期刊：
影响因子：
--
通讯作者：
J. Boyar;Philip Matthews;R. Peralta
中科院分区：
文献类型：
--
作者：
J. Boyar;Philip Matthews;R. Peralta
我们研究了最短线性规划（SLP）问题的复杂性，这是最小化计算一组线性形式所需的线性运算的数量。证明了SLP是NP-困难的。此外，相应的决策问题的一个特殊情况被证明是MaxSNP-Complete.算法产生的取消免费的直线程序，其中从来没有任何取消的变量在GF（2），已被提出的电路最小化的各种密码应用。我们表明，这样的算法具有至少3/2的近似比，因此不能期望产生最佳的解决方案，非平凡的输入。
We study the complexity of the Shortest Linear Program (SLP) problem, which is to minimize 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 beMaxSNP-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.