J4 ›› 2011, Vol. 33 ›› Issue (9): 81-87.
• 论文 • 上一篇 下一篇
韦〓立，许道云
收稿日期:
修回日期:
出版日期:
发布日期:
作者简介:
基金资助:
国家自然科学基金资助项目（60863005）
WEI Li，XU Daoyun
Received:
Revised:
Online:
Published:
摘要：
本文介绍了性质测试的基本原理，分析了用性质测试方法解决参数化问题的可行性，并将同构性质进行了参数化。研究了二元关系的性质测试以及参数化框架同构性质的测试问题，对固定的距离参数，证明了测试复杂性低于标准判定程序的复杂性。
关键词: 性质测试, 二元关系, 参数化, 同构性质, 询问复杂性
Abstract:
The basic principle of property testing is introduced, the possibility of using property testing methods to solve parameterized problems is analyzed, and then the isomorphism properties are parameterized. It studies the property testing of binary relations and parameterized framework isomorphism properties. For a fixed distance parameter, it proves that the testing complexity is better than the complexity of exact decision procedures for every property studied.
Key words: property test;binary relation;parameterized;isomorphism;query complexity
韦〓立，许道云. 二元关系的性质测试及其复杂性分析[J]. J4, 2011, 33(9): 81-87.
WEI Li，XU Daoyun. Property Testing of Binary Relations and Its Complexity Analysis〖[J]. J4, 2011, 33(9): 81-87.
0 / / 推荐
导出引用管理器 EndNote|Ris|BibTeX
链接本文: http://joces.nudt.edu.cn/CN/
http://joces.nudt.edu.cn/CN/Y2011/V33/I9/81
