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

项目名称： 测试一阶逻辑可定义图性质

项目编号： No.61309006

项目类型： 青年科学基金项目

立项/批准年度： 2014

项目学科： 自动化技术、计算机技术

项目作者： 韦立

作者单位： 贵州师范大学

项目金额： 22万元

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

中文关键词： 性质测试；度有界图同构；抗量子计算密码；水印算法；

英文摘要： 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.

英文关键词： property testing；bounded-degree graph isomorphism；post-quantum cryptography；waterkmarking algorithm；