取定s的严格d-正则随机(3,2s)-SAT问题的可满足临界

3-CNF公式的随机难解实例生成对于揭示3-SAT问题的难解实质和设计满足性测试的有效算法有着重要意义.对于整数k>2和s>0,如果在一个k-CNF公式中每个变量正负出现次数均为s,则称该公式是严格正则（k,2s）-CNF公式.受严格正则（k,2s）-CNF公式的结构特征启发,提出每个变量正负出现次数之差的绝对值均为d的严格d-正则（k,2s）-CNF公式,并使用新提出的SDRRK2S模型生成严格d-正则随机（k,2s）-CNF公式.取定整数5<s<11,模拟实验显示,严格d-正则随机（3,2s）-SAT问题存在SAT-UNSAT相变现象和HARD-EASY相变现象.因此,立足于3-CNF公式的随机难解实例生成,研究了严格d-正则随机（3,2s）-SAT问题在s取定时的可满足临界.通过构造一个特殊随机实验和使用一阶矩方法,得到了严格d-正则随机（3,2s）-SAT问题在s取定时可满足临界值的一个下界.模拟实验结果验证了理论证明所得下界的正确性.     

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)的研究有助于在更强正则约束条件下构造难解实例.     

随机正则(k,r)-SAT问题的可满足临界

研究k-SAT问题实例中每个变元恰好出现r=2s次,且每个变元对应的正、负文字都出现s次的严格随机正则（k,r）-SAT问题.通过构造一个特殊的独立随机实验,结合一阶矩方法,给出了严格随机正则（k,r）-SAT问题可满足临界值的上界.由于严格正则情形与正则情形的可满足临界值近似相等,因此得到了随机正则（k,r）-SAT问题可满足临界值的新上界.该上界不仅小于当前已有的随机正则（k,r）-SAT问题的可满足临界值上界,而且还小于一般的随机k-SAT问题的可满足临界值.因此,这也从理论上解释了在相变点处的随机正则（k,r）-SAT问题实例通常比在相应相变点处同规模的随机k-SAT问题实例更难满足的原因.最后,数值分析结果验证了所给上界的正确性.     

多文字可满足SAT问题的相变点上界

可满足(SAT)问题是指：是否存在一组布尔变元赋值,使得随机合取范式(CNF)公式中每个子句至少有1个文字为真。多文字可满足SAT问题是指：是否存在一组布尔变元赋值,使得随机CNF公式中每个子句至少有2个文字为真。此问题仍然是一个NP难问题。定义约束密度α为CNF公式子句数与变元数之比,对该问题的相变点上界α^*进行了研究。如果α>α^*,则多文字可满足SAT问题高概率不可满足。通过一阶矩一个简单的推断,可以证明α^*=-ln 2/ln(1-(k+1)/2^k),当k=3时,α^*=1。利用Kirousis等人的局部最大值技术,提升了多文字可满足3-SAT问题的相变点上界α^*=0.7193。最后,选择了大量数据进行实验验证,结果表明,理论结果与实验结果相吻合。     

On optimizing the satisfiability (SAT) problem

1IntroductionThesatisfiability(SAT)problemistodeterminewhetherthereexistsanassignmentofvaluesin{0,1}toasetofBooleanvariables{x1,xm}thatmakesaconjunctivenormalform(CNF)formulatrue.ThesatisfiabilityproblemofaCNFformulawithatmostlliteralsineachclauseiscalledthel-SATproblem.Theoretically,for>3,theSATproblemisawell-knownNP-completeproblem.Andthus,thereexistsnopolynomialtimealgorithmfortheSATproblemontheassumptionthatPNP.Ontheotherhand,theSATproblemisfundamentalinsolvingmanypracticalprob…     

2-3-SAT问题相变现象剖析及其应用

3-SAT问题有一个非常奇妙的相变现象.对于固定的变量数N，合取范式的可满足概率随着子句个数K的变化而发生剧烈的变化;当K≈4.3*N 时,可满足概率急剧地从1变为0.相变现象决定了问题的难易分布,对于快速求解算法的设计有着非常重要的意义.文章着重讨论了SAT问题的更一般形式，即2-3-SAT问题的相变现象.研究了相变点处的2-子句和3-子句个数的关系，发现了2-子句和3-子句在约束能力意义下的当量关系，并提出了如何有效地利用2-3-SAT的相变现象.     

一类可分离SAT问题的O(1.890n)精确算法

布尔可满足性问题（SAT）是指对于给定的布尔公式,是否存在一个可满足的真值指派.这是第1个被证明的NP完全问题,一般认为不存在多项式时间算法,除非P=NP.学者们大都研究了子句长度不超过k的SAT问题（k-SAT）,从全局搜索到局部搜索,给出了大量的相对有效算法,包括随机算法和确定算法.目前,最好算法的时间复杂度不超过O（（2-2/k）ⁿ）,当k=3时,最好算法时间复杂度为O（1.308ⁿ）.而对于更一般的与子句长度k无关的SAT问题,很少有文献涉及.引入了一类可分离SAT问题,即3-正则可分离可满足性问题（3-RSSAT）,证明了3-RSSAT是NP完全问题,给出了一般SAT问题3-正则可分离性的O（1.890ⁿ）判定算法.然后,利用矩阵相乘算法的研究成果,给出了3-RSSAT问题的O（1.890ⁿ）精确算法,该算法与子句长度无关.     

Exact 3-satisfiability is decidable in time O(20.16254n)

Let F = C ₁ C _m be a Boolean formula in conjunctive normal form over a set V of n propositional variables, s.t. each clause C _i contains at most three literals l over V. Solving the problem exact 3-satisfiability (X3SAT) for F means to decide whether there is a truth assignment setting exactly one literal in each clause of F to true (1). As is well known X3SAT is NP-complete [6]. By exploiting a perfect matching reduction we prove that X3SAT is deterministically decidable in time O(2^0.18674n ). Thereby we improve a result in [2,3] stating X3SAT O(2^0.2072n ) and a bound of O(2^0.200002n ) for the corresponding enumeration problem #X3SAT stated in a preprint [1]. After that by a more involved deterministic case analysis we are able to show that X3SAT O(2^0.16254n ).An extended abstract of this paper was presented at the Fifth International Symposium on the Theory and Applications of Satisfiability Testing (SAT 2002).     

Security of Wang et al.''s group-oriented (t,n) threshold signature schemes with traceable signers

This paper describes a new forgery attack on the group-oriented (t,n) threshold signature schemes proposed by Wang et al. Our attack is more fundamental than Tseng–Jan's attack in the sense that it cannot be recognized or blocked at the designated clerk level of the signature schemes.     

Multiobjective constructive heuristics for the 1/3 variant of the time and space assembly line balancing problem: ACO and random greedy search

In this work we present two new multiobjective proposals based on ant colony optimisation and random greedy search algorithms to solve a more realistic extension of a classical industrial problem: time and space assembly line balancing. Some variants of these algorithms have been compared in order to find out the impact of different design configurations and the use of heuristic information. Good performance is shown after applying every algorithm to 10 well-known problem instances in comparison to NSGA-II. In addition, those algorithms which have provided the best results have been employed to tackle a real-world problem at the Nissan plant, located in Spain.     

Microstructural,dielectric and piezoelectric properties of low-temperature sintering Pb(Co1/2W1/2)O3–Pb(Mn1/2Nb2/3)O3–Pb(Zr,Ti)O3 ceramics with the addition of Li2CO3 and Bi2O3

In this study, in order to develop the low-temperature sintering ceramics for multilayer piezoelectric devices, Pb(Co_1/2W_1/2)O₃–Pb(Mn_1/2Nb_2/3)O₃–Pb(Zr,Ti)O₃ (PCW–PMN–PZT) ceramics doped with Li₂CO₃, Bi₂O₃ and CuO as sintering aids were manufactured, and their microstructural, dielectric and piezoelectric properties were investigated. When the only CuO was added, specimens could not be sintered below 980 °C. However, when Li₂CO₃ and Bi₂O₃ with CuO were simultaneously added to the basic composition ceramics, specimens could be sintered below 980 °C. The addition of Li₂CO₃ and Bi₂O₃ were proved to lower sintering temperature of piezoelectric ceramics due to the effect of Li₂CO₃–Bi₂O₃ liquid phase. Piezoelectric properties of Li₂CO₃ and Bi₂O₃ added specimens showed higher values than those of the only CuO added specimens. At 0.2 wt% Li₂CO₃ and 0.3 wt% Bi₂O₃ added specimen sintered at 920 °C, the dielectric constant (ɛ_r) of 1457, electromechanical coupling factor (k_p) of 0.56 and mechanical quality factor (Q_m) of 1000 were shown, respectively. It is considered that these values are suitable for piezoelectric device application such as multilayer piezoelectric transformer and ultrasonic vibrator with pure Ag internal electrode.     

Necessary and sufficient conditions on Q ( = C( I + PC)) for stabilization of the linear feedback system S(P, C)

We find the following necessary and sufficient conditions for Q (:=C(I+PC)⁻¹) to -stabilize the standard linear time-invariant unity feedback system S(P, C) where P has the l.c.f. (D_pl, N_pl) and the r.c.f. (N_pr, D_pr); and is a principal ideal domain. (i) Q must have elements in (ii) (resp. (iii)) Q must factorize in with D_pr, (resp. D_pl) as a left (resp. right) factor and (iv) (I – QP) must factor in with D_pr, as a left factor.     

On the L(2, 1)-labelling of block graphs

The distance-two labelling problem of graphs was proposed by Griggs and Roberts in 1988, and it is a variation of the frequency assignment problem introduced by Hale in 1980. An L(2, 1)-labelling of a graph G is an assignment of non-negative integers to the vertices of G such that vertices at distance two receive different numbers and adjacent vertices receive different and non-consecutive integers. The L(2, 1)-labelling number of G, denoted by λ(G), is the smallest integer k such that G has a L(2, 1)-labelling in which no label is greater than k.

In this work, we study the L(2, 1)-labelling problem on block graphs. We find upper bounds for λ(G) in the general case and reduce those bounds for some particular cases of block graphs with maximum clique size equal to 3.     

Quaternion representations of the O(3) group, and their applications in robotics

Abstract algebraic methods for solving different mathematical tasks have found widespread applications in theoretical physics and in several technical applications. Though group theory can be used to achieve the most simple and transparent formulation of different tasks, it is not very well known by engineers. The aim of this paper is to discuss quaternion representations of the O⁺(3) Lie group from the aspect of robotics. The main features of these representations, as well as their advantages over the pure 3 × 3 matrix (self-)representation, are discussed in the formulation and solution of the direct and inverse kinematic tasks for robots of general wrist-joint structure. To illustrate the convenience of quaternion formulations a particular solution of the inverse kinematic task has been developed on the basis of the concept of non-Euclidean (curved) spaces. A possible Hopfield-type neural-network application appropriate to the proposed solution is also considered.     

Reconstructing (h,v)-convex 2-dimensional patterns of objects from approximate horizontal and vertical projections

The problem of reconstructing a pattern of an object from its approximate discrete orthogonal projections in a 2-dimensional grid, may have no solution because the inaccuracy in the measurements of the projections may generate an inconsistent problem. To attempt to overcome this difficulty, one seeks to reconstruct a pattern with projection values having possibly some bounded differences with the given projection values and minimizing the sum of the absolute differences.

This paper addresses the problem of reconstructing a pattern with a difference at most equal to +1 or −1 between each of its projection values and the corresponding given projection value. We deal with the case of patterns which have to be horizontally and vertically convex and the case of patterns which have to be moreover connected, the so-called convex polyominoes. We show that in both cases, the problem of reconstructing a pattern can be transformed into a Satisfiability (SAT) Problem. This is done in order to take advantage of the recent advances in the design of solvers for the SAT Problem. We show, experimentally, that by adding two important features to CSAT (an efficient SAT solver), optimal patterns can be found if there exist feasible ones. These two features are: first, a method that extracts in linear time an optimal pattern from a set of feasible patterns grouped in a generic pattern (obtaining a generic pattern may be exponential in the worst case) and second, a method that computes actively a lower bound of the sum of absolute differences that can be obtained from a partially defined pattern. This allows to prune the search tree if this lower bound exceeds the best sum of absolute differences found so far.     

On the uniform finite generation of SO(n, )

A Lie group G, generated by two one-parameter subgroups is said to be uniformly finitely generated by them if there exists a positive integer N such that every element of G can be expressed as a product of at most N elements chosen alternately from the two one-parameter subgroups. In this paper we construct pairs of generators of so(n) whose one-parameter subgroups uniformly finitely generate SO(n) and as a consequence, we put an upper bound on the number of switches required to join any two points on a manifold M trajectories of two particular vector fields on M.     

The equilibrium phase diagram of the pentaerythritol-pentaglycerine-2-amino-2methyl-1,3, propanediol (PE-PG-AMPL) system

Polyalcohols and amines have been considered as potential thermal energy storage materials, owing to their energetic solid-solid phase transitions. In this paper, we present equilibrium phase diagram of Pentaerythritol (PE)–Pentaglycerine (PG)– 2-amino-2methyl-1,3, propanediol (AMPL) ternary system that has been thermodynamically assessed using the CALPHAD method. A special class of, so called, “Plastic Crystals” have tetrahederally configured molecules with O–H⋯O or N–H⋯O layered or chained bonds in the low temperature phase, and store latent heat of transformation during solid-solid phase change in orientationally disordered crystals at higher temperatures. For example, in polyalcohols, there are O–H⋯O bond rotations around the C–C bonds that are responsible for storing large amounts of solid state phase change energy. Several binary equilibrium phase diagrams of polyalcohols, amines and combination thereof have been calculated and experimentally validated. We only know of three ternary phase diagram of these plastic crystals reported, to the best of knowledge. In the thermodynamic calculations of thePE-PG-AMPL system, we used the binary phase diagram experimental data for the optimization and calculation of excess energies. The binary systems have been optimized using regular and sub-regular solution models. The binaries as well as the ternary system have been calculated from room temperature to the liquid phase. The solution phases are modeled as substitutional solutions, in which the excess Gibbs energies are expressed by the Redlich–Kister–Muggianu polynomial. There is a very good agreement between previously reported experimental data and the calculated phase diagrams.     

ZnX_2-AgX(X=Cl,Br)体系的热力学评估

锌银的卤化物熔盐在电池、光学玻璃等方面具有重要的用途,而含卤化锌熔盐因其强烈吸水性和易玻璃化,相图实验测试大受限制。本文利用CALPHAD(Calculation of Phase Diagram)技术,热力学评估计算了ZnX_2-AgX(X=Cl,Br)体系在整个成分范围内的平衡相图,建立了相图与热力学数据库。评估过程中均采用双亚晶格离子溶液模型(Ag~+)_p:(X~-,ZnX_2)_Q描述体系液相结构。通过对已有的相图和热力学实验数据的精确评估,优化计算了ZnCl_2-AgCl体系在768 K,ZnBr_2-AgBr体系在773 K时的液相混合焓,分别获得自洽的热力学参数,计算结果与实验值非常吻合。     

La2O3施主对(MgCoNi))O系材料 导电性能的影响

对少量Ｌａ２Ｏ３施主掺杂的（ＭｇＣｏＮｉ）Ｏ系样品在不同测试温度下的电导与氧分压关系进行了研究，实验发现，施主杂质有两方面的作用当施主含量较低时，以缺位补偿为主；当施主含量较高时，电子实偿占优势，随着施主含量的增加，由缺位补偿向电子补偿过渡，表明施主对材料的高温缺陷结构具有相当重要的影响，缺陷结构受测试温度的影响也很明显。