测试一阶逻辑可定义图性质

In property testing, it requires to design a probabilistic oracle algorithm which with high probability accepts inputs that satisfying property P and rejects inputs that are far from satisfying it, for the predetermined property P. This relaxation allows for very efficient testing algorithms, whose complexity is sublinear in the input size and in many cases independent of the input size. We focus on the researching of testing properties that definable on finite graphs by sentences of first order logic. It concludes . (a) investigating property testing of properties that definable on finite graphs by sentences of fragment of first order logic, design and analysis of testing algorithms for such properties. The fragments considered include $\exists, \wedge $-FO，$\exists, \forall, \wedge$-FO, $\exists, \forall, \wedge, \vee$-FO, $\exists, \forall, \neq$-FO，etc. . (b)investigating phase transition for definable graph property and the relations between phase transition and testing algorithm of the property.. (c)investigating the parameterized complexity of model checking problems over finite graph that parameterized by the width of the sentence and degree of graph.

在性质测试中，给定一个性质P，要求设计一个概率神谕算法A，对任意输入对象f，算法询问关于f的局部信息，满足：以较大概率接受具备性质P的对象，以较大概率拒绝远离性质P的对象。本项目研究有限图上一阶逻辑可定义性质的测试问题。主要研究内容包括：$\exists,\wedge$-FO，$\exists,\forall,\wedge$-FO, $\exists,\forall,\wedge,\vee$-FO, $\exists,\forall,\neq$-FO等一阶逻辑片段可定义图性质的测试问题，设计并分析测试方案的复杂性；随机图模型中上述一阶逻辑片段可定义性质的相变，并借助性质的阈值来设计出其测试方案；从公式宽度，图的度等角度设置参数，探索相应一阶逻辑的参数化模型检测问题的参数复杂性。

本项目旨在研究图性质的测试问题。.研究了度有界图同构测试问题，探讨了两种情形下该问题的具备双边误差的测试算法，并给出其询问复杂性的下界。..由于性质测试领域理论性极强，研究过程中碰到了许多难以攻克的理论问题，在其它方面做了一些研究，并取得了一些不错的成果，主要如下：..在密码方面，将多变量公钥密码 MI体制与基于 QC-LDPC码的纠错码密码串联起来，提出了一种新的具有80比特安全性的抗量子计算的多变量公钥密码体制，分析表明该体制是安全有效的，具有私钥较小的优点。..在图像水印方面，提出若干水印算法，包括一个新的空域强鲁棒零水印方案、基于三维离散余弦变换的鲁棒彩色图像水印算法、基于3D-DCT和SVD的鲁棒彩色图像水印算法、基于图像插值的大容量可逆水印算法等，仿真实验表明，这些算法优于同种类型的算法。