新书推介：《语义网技术体系》
作者：瞿裕忠，胡伟，程龚
   XML论坛     W3CHINA.ORG讨论区     >>计算机科学论坛<<     SOAChina论坛     Blog     开放翻译计划     新浪微博  
 
  • 首页
  • 登录
  • 注册
  • 软件下载
  • 资料下载
  • 核心成员
  • 帮助
    		•   Add to Google

    >> 本版讨论Semantic Web(语义Web,语义网或语义万维网, Web 3.0)及相关理论，如：Ontology(本体,本体论), OWL(Web Ontology Langauge,Web本体语言), Description Logic(DL, 描述逻辑),RDFa,Ontology Engineering等。
    [返回] 计算机科学论坛 → W3CHINA.ORG讨论区 - Web新技术讨论 → 『 Semantic Web(语义Web)/描述逻辑/本体 』 → 请教！DL推理复杂度 ◇查看新帖 ◇ 用户列表 ◇

      发表一个新主题  发表一个新投票  回复主题  (订阅本版) 您是本帖的第 8862 个阅读者浏览上一篇主题  刷新本主题   树形显示贴子　浏览下一篇主题
     * 贴子主题： 请教！DL推理复杂度 举报  打印  推荐  IE收藏夹 
       本主题类别:     
     river_hh 美女呀，离线，快来找我吧！
      
      
      威望：1
      等级：大三(要不要学学XML呢?)
      文章：64
      积分：787
      门派：XML.ORG.CN
      注册：2004/11/16

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给river_hh发送一个短消息 把river_hh加入好友 查看river_hh的个人资料 搜索river_hh在『 Semantic Web(语义Web)/描述逻辑/本体 』的所有贴子 引用回复这个贴子 回复这个贴子 查看river_hh的博客楼主
    发贴心情 请教！DL推理复杂度

    不同的dl逻辑系统的推理复杂度不同，经常见到下面符号，
    PSpace-complete, ExpTime-complete, co-NExpTime-complete
    我的理解是：
    PSpace是指计算单元的是多项式的，
    ExpTime是计算时间是指数级的，
    NExpTime是非确定的指数时间，
    不知道正不正确，
    还有co表示什么？

       收藏   分享  
    顶(0)
      




    ----------------------------------------------
    现在不用恶补逻辑了。。。
    因为终于毕业了。。。

    http://bloghuanghe.blogcn.com

    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/4/12 19:02:00
     
     wason21cn 帅哥哟，离线，有人找我吗？
      
      
      等级：大四(GRE考了1400分!)
      文章：117
      积分：1001
      门派：W3CHINA.ORG
      注册：2004/11/17

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给wason21cn发送一个短消息 把wason21cn加入好友 查看wason21cn的个人资料 搜索wason21cn在『 Semantic Web(语义Web)/描述逻辑/本体 』的所有贴子 引用回复这个贴子 回复这个贴子 查看wason21cn的博客第2楼
    发贴心情 
    co 即complement， 关于楼主对这些复杂度的理解，大致上可以说是正确的，但是楼主如果能给出更加精确的定义，就更好了， 比如对于一个问题，说解决他的复杂度是PSpace，该怎样理解？  我们假设对于一个问题，他的输入的长度是n，如果存在一个多项式（polynomial）p，能够在p（n）计算单元下解决这个问题，就说是PSpace的。 所以说解决一个问题通常都要考虑到它的输入长度，然后再说再什么复杂度下解决.

    关于complete的问题，下面这个帖子讨论了一些，你可以参考
    http://bbs.w3china.org/dispbbs.asp?boardID=2&ID=29725

    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/4/12 19:37:00
     
     river_hh 美女呀，离线，快来找我吧！
      
      
      威望：1
      等级：大三(要不要学学XML呢?)
      文章：64
      积分：787
      门派：XML.ORG.CN
      注册：2004/11/16

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给river_hh发送一个短消息 把river_hh加入好友 查看river_hh的个人资料 搜索river_hh在『 Semantic Web(语义Web)/描述逻辑/本体 』的所有贴子 引用回复这个贴子 回复这个贴子 查看river_hh的博客第3楼
    发贴心情 
    那co-NExpTime-complete指的是什么？

    ----------------------------------------------
    现在不用恶补逻辑了。。。
    因为终于毕业了。。。

    http://bloghuanghe.blogcn.com

    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/4/12 19:47:00
     
     river_hh 美女呀，离线，快来找我吧！
      
      
      威望：1
      等级：大三(要不要学学XML呢?)
      文章：64
      积分：787
      门派：XML.ORG.CN
      注册：2004/11/16

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给river_hh发送一个短消息 把river_hh加入好友 查看river_hh的个人资料 搜索river_hh在『 Semantic Web(语义Web)/描述逻辑/本体 』的所有贴子 引用回复这个贴子 回复这个贴子 查看river_hh的博客第4楼
    发贴心情 
    complement在时间复杂度中表示什么？

    BTW，我读了“关于complete的问题，下面这个帖子讨论了一些，你可以参考
    http://bbs.w3china.org/dispbbs.asp?boardID=2&ID=29725
    ”
    非常精彩

    ----------------------------------------------
    现在不用恶补逻辑了。。。
    因为终于毕业了。。。

    http://bloghuanghe.blogcn.com

    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/4/12 19:52:00
     
     river_hh 美女呀，离线，快来找我吧！
      
      
      威望：1
      等级：大三(要不要学学XML呢?)
      文章：64
      积分：787
      门派：XML.ORG.CN
      注册：2004/11/16

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给river_hh发送一个短消息 把river_hh加入好友 查看river_hh的个人资料 搜索river_hh在『 Semantic Web(语义Web)/描述逻辑/本体 』的所有贴子 引用回复这个贴子 回复这个贴子 查看river_hh的博客第5楼
    发贴心情 
    我在wiki上查到关于时间复杂度（complexity class）的详细说明，
    http://www.answers.com/main/ntquery?method=4&dsid=2222&dekey=Complexity+class&curtab=2222_1
    正在阅读中。。。

    ----------------------------------------------
    现在不用恶补逻辑了。。。
    因为终于毕业了。。。

    http://bloghuanghe.blogcn.com

    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/4/12 19:57:00
     
     wason21cn 帅哥哟，离线，有人找我吗？
      
      
      等级：大四(GRE考了1400分!)
      文章：117
      积分：1001
      门派：W3CHINA.ORG
      注册：2004/11/17

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给wason21cn发送一个短消息 把wason21cn加入好友 查看wason21cn的个人资料 搜索wason21cn在『 Semantic Web(语义Web)/描述逻辑/本体 』的所有贴子 引用回复这个贴子 回复这个贴子 查看wason21cn的博客第6楼
    发贴心情 
    通常对于问题的解决，我们可以直接去寻找解决问题的答案，或者通过寻找不能解决问题的答案，然后取相反，而得到问题的答案，比如说，对于一个班级，我要找所有的男生，我可以直接找所有的男生，直接得到答案，或者我先通过找女生，然后取女生的complement，就得到男生（当然前提条件是全部同学是一个整体）
    那么如果说解决一个问题的复杂度是co-NexpTime-complete， 首先，我们说要把这个问题给解决（或者说找到解决这个问题的solution）只能在NexpTime这个复杂度给解决，所以是complete的，所以对于co-NexpTime-complete来说，你可以这样理解，要找到不能解决这个问题的solution，是NexpTime－complete的。
    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/4/12 20:18:00
     
     superc_7 帅哥哟，离线，有人找我吗？射手座1983-12-15
      
      
      威望：6
      等级：研一(彻夜钻研J2EE)
      文章：504
      积分：3396
      门派：XML.ORG.CN
      注册：2005/4/22

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给superc_7发送一个短消息 把superc_7加入好友 查看superc_7的个人资料 搜索superc_7在『 Semantic Web(语义Web)/描述逻辑/本体 』的所有贴子 点击这里发送电邮给superc_7  引用回复这个贴子 回复这个贴子 查看superc_7的博客第7楼
    发贴心情 
    嗯
    长知识了
    谢谢楼上诸位
    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/4/13 12:27:00
     
     wolfel 帅哥哟，离线，有人找我吗？
      
      
      威望：2
      等级：计算机学士学位
      文章：280
      积分：2178
      门派：W3CHINA.ORG
      注册：2005/3/17

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给wolfel发送一个短消息 把wolfel加入好友 查看wolfel的个人资料 搜索wolfel在『 Semantic Web(语义Web)/描述逻辑/本体 』的所有贴子 引用回复这个贴子 回复这个贴子 查看wolfel的博客第8楼
    发贴心情 
    哪个描述逻辑是co-NEXP-Complete?

    我还没有见过，提示一下？

    ----------------------------------------------
    Correct reasoning is our business.

    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/4/17 23:21:00
     
     wason21cn 帅哥哟，离线，有人找我吗？
      
      
      等级：大四(GRE考了1400分!)
      文章：117
      积分：1001
      门派：W3CHINA.ORG
      注册：2004/11/17

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给wason21cn发送一个短消息 把wason21cn加入好友 查看wason21cn的个人资料 搜索wason21cn在『 Semantic Web(语义Web)/描述逻辑/本体 』的所有贴子 引用回复这个贴子 回复这个贴子 查看wason21cn的博客第9楼
    发贴心情 
    ALCQI, ALCQIO都是co-NExpTime-complete
    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/4/17 23:38:00
     
     wolfel 帅哥哟，离线，有人找我吗？
      
      
      威望：2
      等级：计算机学士学位
      文章：280
      积分：2178
      门派：W3CHINA.ORG
      注册：2005/3/17

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给wolfel发送一个短消息 把wolfel加入好友 查看wolfel的个人资料 搜索wolfel在『 Semantic Web(语义Web)/描述逻辑/本体 』的所有贴子 引用回复这个贴子 回复这个贴子 查看wolfel的博客第10楼
    发贴心情 
    哦～这个...很少注意

    ----------------------------------------------
    Correct reasoning is our business.

    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/4/18 0:08:00
     
     GoogleAdSense
      
      
      等级：大一新生
      文章：1
      积分：50
      门派：无门无派
      院校：未填写
      注册：2007-01-01
    给Google AdSense发送一个短消息 把Google AdSense加入好友 查看Google AdSense的个人资料 搜索Google AdSense在『 Semantic Web(语义Web)/描述逻辑/本体 』的所有贴子 访问Google AdSense的主页 引用回复这个贴子 回复这个贴子 查看Google AdSense的博客广告
    2025/10/6 10:56:50

    本主题贴数13，分页： [1] [2]

    管理选项： 修改tag | 锁定 | 解锁 | 提升 | 删除 | 移动 | 固顶 | 总固顶 | 奖励 | 惩罚 | 发布公告
    W3C Contributing Supporter! W 3 C h i n a ( since 2003 ) 旗 下 站 点
    苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》
    		 93.750ms