P问题与NP问题的关系
P问题与NP问题的关系
定理5.P⊆NPP \subseteq NPP⊆NP.
即，所有的P问题都是NP问题。当一个问题是P问题时，我们可以在多项式时间内求出问题的解。若要验证一个解（记为t1）是否正确时，只需使用多项式时间求解出这个问题的解（记为t2），然后将t1和t2做比较即可验证答案是否正确。即，可以利用多项式时间验证答案正确与否。因此，P问题也是NP问题。可以看到，三元可满足性问题（3-SAT）、独立集问题、集合覆盖问题都是NP问题。
【讨论：P=NP?】
对于这个问题，还没有人利用一种有效的方法证明。目前计算机界普遍相信P≠NP。所以P问题是NP问题的真子集。
,.:heart_suit:,.,.:heart_suit:,.,
文件下载
评论信息
其他资源
- STM32F103C8T6核心板程序FreeRTOS移植成功
- LabVIEW 拖动图片和自动缩放图片
- 历年电赛信号源类题目分析
- AD7746采集程序
- C语言一个子集编译器词法语法分析中间及目标代码
- 数据库大作业 快递管理系统
- 板球 串级.zip
- MFC编程技巧与范例详解PDF(无水印 带书签)+源代码
- Java版socket编程 局域网聊天工具
- 历年美赛题目及翻译
- Approximation_algorithms.pdf
- 性能测试基础--（CPU）
- Spectrum-Oriented FFBP Algorithm in Quasi-Polar Grid for SAR Imaging on Maneuvering Platform
- ARM9嵌入式系统硬件设计指南(上).pdf
- 电子科技大学《信号检测与估计》期末考题2（含答案）.pdf
- 移动式输油管线管件设计模型研究
- 金蝶银企中间件750版本接口规范_V1.0.0
- 青岛宣传——网页制作
- SpringBoot学习笔记——尚硅谷
- 0~220V电压表程序
- 模拟电子电路王远答案
- 个人信息管理平台（内含数据库）
免责申明
【只为小站】的资源来自网友分享，仅供学习研究，请务必在下载后24小时内给予删除，不得用于其他任何用途，否则后果自负。基于互联网的特殊性，【只为小站】 无法对用户传输的作品、信息、内容的权属或合法性、合规性、真实性、科学性、完整权、有效性等进行实质审查；无论 【只为小站】 经营者是否已进行审查，用户均应自行承担因其传输的作品、信息、内容而可能或已经产生的侵权或权属纠纷等法律责任。
本站所有资源不代表本站的观点或立场，基于网友分享，根据中国法律《信息网络传播权保护条例》第二十二条之规定，若资源存在侵权或相关问题请联系本站客服人员，zhiweidada#qq.com，请把#换成@，本站将给予最大的支持与配合，做到及时反馈和处理。关于更多版权及免责申明参见 版权及免责申明
本站所有资源不代表本站的观点或立场，基于网友分享，根据中国法律《信息网络传播权保护条例》第二十二条之规定，若资源存在侵权或相关问题请联系本站客服人员，zhiweidada#qq.com，请把#换成@，本站将给予最大的支持与配合，做到及时反馈和处理。关于更多版权及免责申明参见 版权及免责申明