什么是多项式时间？什么是NP问题？

青旅半醒 2022-10-05 09:57 160阅读 0赞

参考：[https://zhidao.baidu.com/question/68492427.html?qbl=relate\_question\_0&word=%B6%E0%CF%EE%CA%BD%CA%B1%BC%E4%C4%DA][https_zhidao.baidu.com_question_68492427.html_qbl_relate_question_0_word_B6_E0_CF_EE_CA_BD_CA_B1_BC_E4_C4_DA]

[https://blog.csdn.net/wxdsdtc831/article/details/7942435][https_blog.csdn.net_wxdsdtc831_article_details_7942435]

**什么是NP问题**

**概念1:**

**在计算机学科中，存在多项式时间的算法的一类问题，称之为P类问题；而像梵塔问题、推销员旅行问题、（命题表达式）可满足问题这类，至今没有找到多项式时间算法解的一类问题，称之为NP类问题。**

就是问题需要的**时间**（复杂度）与问题的**规模之间是多项式关系**。  
举个例子：

现在从n阶图中找两点的最短路径，复杂度为**n^2**级别（即O(n^2)），而**n^2**对于**n**是多项式（单项式当然也算），这就称为是多项式复杂度，或者多项式时间，其中问题（算法）的**规模是n**。

如果某一个算法的规模是n，但是复杂度比如是**2^n**，**写不成n的多项式**，那就不是多项式时间。

[https_zhidao.baidu.com_question_68492427.html_qbl_relate_question_0_word_B6_E0_CF_EE_CA_BD_CA_B1_BC_E4_C4_DA]: https://zhidao.baidu.com/question/68492427.html?qbl=relate_question_0&word=%B6%E0%CF%EE%CA%BD%CA%B1%BC%E4%C4%DA
[https_blog.csdn.net_wxdsdtc831_article_details_7942435]: https://blog.csdn.net/wxdsdtc831/article/details/7942435

发表评论取消回复

表情：

评论列表（有 0 条评论，160人围观）

还没有评论，来说两句吧...

相关阅读

相关什么是P问题、NP问题和NPC问题

本文主要介绍什么是P问题、NP问题和NPC问题，这几个问题在课本中反复出现，并且不好理解，闲余时间进行总结，关系图如下： ![在这里插入图片描述][watermar...

落日映苍穹つ/ 2024年04月18日 23:38/ 0 赞/ 54 阅读

相关 cst是什么时间(Cst是什么检查)

时间格式中的CST和sat是什么？ CST是美国中部标准时间，SAT是智利时间，我顺便把所有时区的缩写附在下面给你吧希望能够帮到你 :D IDLW-1200Inte

比眉伴天荒/ 2023年09月26日 12:51/ 0 赞/ 138 阅读

相关什么是金融界的NP服务？

什么是NP服务？ NP取自new pay的首字母，也就是新支付的意思。 NP服务是一款新业务支付、营销、结算工具，具有延展信用卡账单功能，是中小企业或个人短期融资利器

ゞ浴缸里的玫瑰/ 2023年06月12日 09:51/ 0 赞/ 4 阅读

相关零知识证明之什么是QAP？什么是P/NP、NP完全问题(NPC问题)、NP hard问题？多项式时间

文章目录一、什么是NP问题 1. 多项式时间 2. 关于阶乘 n！ 12字助记词真的安

港控/mmm°/ 2023年01月08日 08:17/ 0 赞/ 158 阅读

相关什么是TPS，什么是QPS，区别是什么？

一、TPS：Transactions Per Second（每秒传输的事物处理个数），即服务器每秒处理的事务数。TPS包括一条消息入和一条消息出，加上一次用户数据库访问。（业务

绝地灬酷狼/ 2022年10月29日 03:22/ 0 赞/ 535 阅读

相关什么是多项式时间？什么是NP问题？

参考：[https://zhidao.baidu.com/question/68492427.html?qbl=relate\_question\_0&word=%B6%E0%

青旅半醒/ 2022年10月05日 09:57/ 0 赞/ 161 阅读

相关什么是P问题、NP问题、NPC问题、NP-hard问题

图片来自一个同事的整理： ![请添加图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA

叁歲伎倆/ 2022年09月15日 06:13/ 0 赞/ 168 阅读

相关【他山之石】【Matrix67】什么是P问题、NP问题和NPC问题

【写在前面：Matrix67同学的很多文章非常好，受益匪浅，开拓你的数学思维，大家可以看一看】这或许是众多OIer最大的误区之一。你会经常看到网

骑猪看日落/ 2022年08月08日 11:44/ 0 赞/ 172 阅读

相关什么是NP问题，什么是NP hard问题，什么是NP完全问题。

http://www.cs.pitt.edu/~ztliu/wordpress/2011/05/np-problem/ 首先解释一下什么是NP问题，什么是NP ha

朴灿烈づ我的快乐病毒、/ 2022年07月15日 02:57/ 0 赞/ 206 阅读

相关什么是响应时间？

这里一般指的是性能测试中性能指标的响应时间；比如发送一个requests请求，返回response的时间是多少；一般时间为200ms; 转载于:https://www.cn

骑猪看日落/ 2022年01月09日 11:37/ 0 赞/ 309 阅读