计算理论第六章计算复杂性2

VIP免费

2025-01-13 2 0 765.87KB 32 页 5.9玖币

侵权投诉

计算理论

第6章计算复杂性

P类

定义：P类是单带DTM在多项式时间内可判定

的语言类。即，

P = TIME()

如：

PATH

RELPRIME

LCFG

NP类

哈密顿路径:

有向图G中经过每个节点恰好一次的有向路

径

哈密顿路径问题：

一个有向图是否包含一条从节点s到t到哈密顿

路径

HAMPATH={ <G,s,t> | 有向图G包含从s到t

的哈密顿路径}

判定是否有Hamiton路径

能找出Hamiton路径

验证Hamilton路径：多项式时间

s t

合数问题

COMPOSITES ={x| x=pq，整数p,q>1}

 验证是否是合数：多项式时间

验证机

语言A={ w |存在字符串c, 算法V接受<w,c> }

算法V称为语言A的验证机(DTM), 若V是多项式

时间，则称A是多项式时间验证机。c称为w是A成

员的资格证书(certificate)或证明(proof)。|c|是|w|

的多项式

HAMPATH ：c是从s到t的哈密顿路径；V是哈密顿路径

验证算法；多项式时间

COMPOSITES：c是x的因子；V是合数验证算法；多项

式时间

NP类

定义:NP类是具有多项式时间验证机的语言类

NP类问题：

 HAMPATH NP

 COMPOSITES  NP

 COMPOSITES  NP （P）

HAMPATH  NP ？

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

5.9 玖币 0人已下载

立即下载 VIP免费下载

摘要：

计算理论第6章计算复杂性P类定义：P类是单带DTM在多项式时间内可判定的语言类。即，P=�TIME(��)如：PATHRELPRIMELCFGNP类哈密顿路径:有向图G中经过每个节点恰好一次的有向路径哈密顿路径问题：一个有向图是否包含一条从节点s到t到哈密顿路径HAMPATH={|有向图G包含从s到t的哈密顿路径}判定是否有Hamiton路径能找出Hamiton路径验证Hamilton路径：多项式时间st合数问题COMPOSITES={x|x=pq，整数p,q>1}验证是否是合数：多项式时间验证机语言A={w|存在字符串c,算法V接受}算法V...

展开>> 收起<<

计算理论第六章计算复杂性2.pdf

共32页,预览7页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

计算理论第六章计算复杂性2

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择:

计算理论第六章 计算复杂性2

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择:

计算理论第六章计算复杂性2