New Complexity Results on Array Contraction and Related Problems

Array contraction is an optimization that transforms array variables into scalar variables within a loop. While the opposite transformation, scalar expansion, is used for enabling parallelism (with a penalty in memory size), array contraction is used to save memory by removing temporary arrays and to increase locality. Several heuristics have already been proposed to perform array contraction through loop fusion and/or loop shifting. But until now, the complexity of the problem was unknown, and no exact approach was available (and even more, only a sufficient condition for array contraction was used). In this paper, we focus on the theoretical aspects of the problem. We prove several NP-complete results that characterize precisely its complexity and we provide an integer linear programming formulation to solve the problem exactly. Our study also proves the NP-completeness of similar problems whose complexity was not established so far.Alain Darte is a researcher with the French National Council for Scientific Research (CNRS). His education includes an Agrégation de Mathématiques in 1992 and Ph.D. degree in computer science in 1993 from the École normale supérieure de Lyon, France. His main scientific interests are in mathematical tools, automatic program transformations, and optimizations for parallelizing compilers and for compiler-based tools used to automatically synthesize hardware accelerators.Guillaume Huard is associate professor at the University Joseph Fourier of Grenoble, France, since Sept. 2002. He has earned a distinction from the AFIT (French association for theoretical computer science) for his Ph.D. thesis in 2002. He is conducting his research whithin the scheduling team of the Apache INRIA project of the ID Laboratory (Grenoble). His main research interests are instruction scheduling, resource constrained scheduling, and memory optimizations.     

k-LSAT(k≥3)是NP-完全的(英文)

合取范式(conjunctive normal form,简称CNF)公式F是线性公式,如果F中任意两个不同子句至多有一个公共变元.如果F中的任意两个不同子句恰好含有一个公共变元,则称F是严格线性的.所有的严格线性公式均是可满足的,而对于线性公式类LCNF,对应的判定问题LSAT仍然是NP-完全的.LCNF≥k是子句长度大于或等于k的CNF公式子类,判定问题LSAT≥k的NP-完全性与LCNF≥k中是否含有不可满足公式密切相关.即LSAT≥k的NP-完全性取决于LCNF≥k是否含有不可满足公式.S.Porschen等人用超图和拉丁方的方法构造了LCNF≥3和LCNF≥4中的不可满足公式,并提出公开问题:对于k≥5,LCNF≥k是否含有不可满足公式?将极小不可满足公式应用于公式的归约,引入了一个简单的一般构造方法.证明了对于k≥3,k-LCNF含有不可满足公式,从而证明了一个更强的结果:对于k≥3,k-LSAT是NP-完全的.     

Complexity of approximation of 3-edge-coloring of graphs

The problem to find a 4-edge-coloring of a 3-regular graph is solvable in polynomial time but an analogous problem for 3-edge-coloring is NP-hard. To make the gap more precise, we study complexity of approximation algorithms for invariants measuring how far is a 3-regular graph from having a 3-edge-coloring. We show that it is an NP-hard problem to approximate such invariants with an error O(n1−ε), where n denotes the order of the graph and 0<ε<1 is a constant.     

d-正则(k,s)-SAT问题的NP完全性

研究具有正则结构的SAT问题是否是NP完全问题,具有重要的理论价值.(k,s)-CNF公式类和正则(k,s)-CNF公式类已被证明存在一个临界函数f(k),使得当s≤f(k)时,所有实例都可满足;当s≥f(k)+1时,对应的SAT问题是NP完全问题.研究具有更强正则约束的d-正则(k,s)-SAT问题,其要求实例中每个变元的正负出现次数之差不超过给定的自然数d.通过设计一种多项式时间的归约方法,证明d-正则(k,s)-SAT问题存在一个临界函数f(k,d),使得当s≤f(k,d)时,所有实例都可满足;当s≥f(k,d)+1时,d-正则(k,s)-SAT问题是NP完全问题.这种多项式时间的归约变换方法通过添加新的变元和新的子句,可以更改公式的子句约束密度,并约束每个变元正负出现次数的差值.这进一步说明,只用子句约束密度不足以刻画CNF公式结构的特点,对临界函数f(k,d)的研究有助于在更强正则约束条件下构造难解实例.     

On the complexity of synthesizing a minimum-weighted supervisor under partial observation

With full observation the problem of synthesizing a minimum-weighted supervisor has been shown polynomial-time solvable. With partial observation the problem becomes NP-hard. In this paper we will show that the decision version of the problem becomes NP-complete when the natural projection is a natural observer. This NP-completeness result is unexpected, considering that the logic supervisor synthesis problem under the same assumption becomes polynomial-time solvable.     

基于三角环的顶点着色问题解法

图的着色问题是一个NP难问题,本文着重探讨无向图的顶点的三色问题,提出了用构造三角环的极大独立集方法判断并尝试给出顶点三色问题的可行解,解决了顶点三色的可满足性问题,克服了以前图遍历过程中的回溯问题,以及由此推论顶点四色和五色问题的极大独立集。     

有不同中断时间代价的一致并行抢先调度问题

提出了具有不同中断时间代价的抢先调度问题(P|ptmn(δi)|Cmax)．该问题在工程任务分配、分布式计算和网络通信等实际问题中有着广泛的应用背景．首先证明了这个问题是一个NP难优化问题．并给出了一个时间复杂度为O(nlogn)的近似算法,其近似度为5／3．算法的特点是结合中断时间δi来应用LPT思想,而不只是把它应用到任务i的执行时间pi上,从而避免了LPT算法在最坏情形下的近似度差的问题．在算法的关键部分,运用了均分的技巧来提高任务执行的并行性,进一步提高了近似度．     

A note on the inclusion problem for szilard languages †

It is shown that the problem of labeling the productions of two regular grammars G ₁ and G ₂ in such a way that the Szilard language of G ₁ is included in the Szilard language of G ₂ is NP-complete.     

Nash Stability in Additively Separable Hedonic Games and Community Structures

We prove that the problem of deciding whether a Nash stable partition exists in an Additively Separable Hedonic Game is NP-complete. We also show that the problem of deciding whether a non trivial Nash stable partition exists in an Additively Separable Hedonic Game with non-negative and symmetric preferences is NP-complete. We motivate our study of the computational complexity by linking Nash stable partitions in Additively Separable Hedonic Games to community structures in networks. Our results formally justify that computing community structures in general is hard. The research is partly sponsored by the company Cofman ().