首页 | 本学科首页   官方微博 | 高级检索  
     

二元关系的性质测试及其复杂性分析
引用本文:韦立,许道云.二元关系的性质测试及其复杂性分析[J].计算机工程与科学,2011,33(9):81.
作者姓名:韦立  许道云
作者单位:贵州大学计算机科学系,贵州贵阳,550025
摘    要:本文介绍了性质测试的基本原理,分析了用性质测试方法解决参数化问题的可行性,并将同构性质进行了参数化。研究了二元关系的性质测试以及参数化框架同构性质的测试问题,对固定的距离参数,证明了测试复杂性低于标准判定程序的复杂性。

关 键 词:性质测试  二元关系  参数化  同构性质  询问复杂性

Property Testing of Binary Relations and Its Complexity Analysis
WEI Li,XU Dao-yun.Property Testing of Binary Relations and Its Complexity Analysis[J].Computer Engineering & Science,2011,33(9):81.
Authors:WEI Li  XU Dao-yun
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.
Keywords:property test  binary relation  parameterized  isomorphism  query complexity
本文献已被 万方数据 等数据库收录!
点击此处可从《计算机工程与科学》浏览原始摘要信息
点击此处可从《计算机工程与科学》下载全文
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号