您好, 欢迎来到 !    登录 | 注册 | | 设为首页 | 收藏本站

什么是计算机科学中的NP-complete?

什么是计算机科学中的NP-complete?

代表 时间。

这意味着可以使用非确定性图灵机(类似于常规图灵机,但还包括非确定性“选择”功能)在多项式时间内解决问题。基本上,解决方案必须 可以 在聚合时间内进行测试 。如果是这样,并且可以使用输入经过修改的给定问题来解决已知的NP问题(可以将NP问题 简化 为给定问题),那么该问题就可以解决NP问题。

解决NP完全问题,最主要的事情是无法以任何已知的方式在多项式时间内解决它。NP-Hard / NP- Complete是一种显示某些类型的问题在现实时间内无法解决方法

编辑:正如其他人指出的那样,通常有NP- Complete问题的近似解决方案。在这种情况下,近似解通常使用特殊符号给出近似边界,该近似符告诉我们近似的接近程度。

其他 2022/1/1 18:14:43 有509人围观

撰写回答


你尚未登录,登录后可以

和开发者交流问题的细节

关注并接收问题和回答的更新提醒

参与内容的编辑和改进,让解决方法与时俱进

请先登录

推荐问题


联系我
置顶