AI 助理
文档备案控制台
开发者社区 华章出版社 文章 正文

《计算复杂性：现代方法》——2.2　归约和NP完全性

2017-05-02 1528
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介：

本节书摘来自华章计算机《计算复杂性：现代方法》一书中的第2章，第2.2节，作者 ［美］桑杰夫·阿罗拉（Sanjeev Arora），博阿兹·巴拉克（Boaz Barak），译 骆吉洲，更多章节内容可以访问云栖社区“华章计算机”公众号查看。

2.2　归约和NP完全性

screenshot

我们怎样才能证明一个语言C至少与另外一个语言B一样难呢？归约的概念是我们完成这种任务的关键工具。

screenshot
screenshot
screenshot
screenshot
screenshot

华章计算机
目录
相关文章
Mr.Meng_95
后端返回base64格式数据转excel格式文件并下载
后端返回base64格式数据转excel格式文件并下载
Mr.Meng_95
786 0
AI研究者手札
|
6月前
|
安全 Java Linux
Java 获取音频文件的持续时间（毫秒级）——摆脱 FFprobe 的纯本地方案（无外部依赖 / 低开销 / 可直接部署）
本文介绍如何在Java中不依赖FFmpeg，通过标准库`javax.sound.sampled`解析WAV、AIFF等音频文件头信息，直接计算毫秒级时长。方案无外部依赖、跨平台、低开销，适合高并发与安全敏感场景，显著优于调用FFprobe的进程方式，是轻量可控的优选方案。
AI研究者手札
454 0
AokSend接口-API
|
人工智能 搜索推荐 大数据
EDM营销是什么意思？
EDM营销是什么意思？
AokSend接口-API
1206 0
游客4jqguaynwz2fs
|
9月前
|
Ubuntu 安全 搜索推荐
揭秘Ubuntu系统的优势，你想知道吗？
对于移动设备，Ubuntu系统还在不断地探索与支持。众多Ubuntu系统的社区和开发人员正在探索Ubuntu系统在移动领域的应用，以提供全新的、更加开放和稳定的移动系统体验。 对于云服务器，Ubuntu系统作为一种轻量级的操作系统，越来越受到云服务提供商的青睐。Ubuntu系统可以作为一种安全和高效的云服务器操作系统，无论在公有云、私有云或混合云里，都可以提供出色的性能和体验。
游客4jqguaynwz2fs
949 0
赵渝强老师
|
8月前
|
数据库
【赵渝强老师】达梦数据库实例的状态
达梦数据库实例包含NORMAL、PRIMARY和STANDBY三种模式，以及MOUNT、OPEN和SUSPEND三种状态。模式之间可在MOUNT状态下相互转换，不同状态与模式适用于数据库的启动、配置及运行需求。
赵渝强老师
411 1
游客3g2isv2zt6tuw
|
10月前
微博批量关注签到发帖脚本，超话发布自动插件，油猴工具实现源码
完整的微博自动化操作油猴脚本实现方案。这个脚本包含批量关注、每日签到、自动发帖和超话发布功能
游客3g2isv2zt6tuw
1049 0
dufadayang
|
前端开发 安全 API
跨域请求的常见场景有哪些？
了解这些常见的跨域请求场景，有助于我们更好地理解和处理跨域问题，通过合理的技术手段和配置来实现跨域资源的安全访问和交互。
dufadayang
626 64
viq5y7h5mbyhk
|
存储 C语言
C语言中的二进制文件与文本文件技术详解
C语言中的二进制文件与文本文件技术详解
viq5y7h5mbyhk
412 0
baker_zhuang
|
存储 物联网 数据安全/隐私保护
Docker安装Mosquitto
这篇文章详细介绍了如何在Docker中安装和配置Mosquitto消息代理服务，包括拉取镜像、创建容器以及配置持久化存储等步骤。
baker_zhuang
2688 0
Docker安装Mosquitto

华章出版社

热门文章

最新文章

  • 1
    MAC下iterm2用密钥登录服务器过程
  • 2
    jsch jar包连接不上ssh报Algorithm negotiation fail 错误
  • 3
    破解当前媒体文件受drm版权保护，无法播放
  • 4
    Microsoft Activation Scripts v3.6 （MAS）激活工具安装教程!中文汉化版(激活工具)
  • 5
    开源大数据周刊-第90期
  • 6
    130 秒揭秘 EDAS 3.0 如何平滑应对突发流量高峰，为您的业务保驾护航
  • 7
    开源大数据技术专场（上午）:Spark、HBase、JStorm应用与实践
  • 8
    LintCode: Combination Sum
  • 9
    poj 3150 Cellular Automaton
  • 10
    DNS根域只有13个的原因
  • 1
    [理论篇-13]AI 编程(AI Coding)—— 从"AI 帮你打字"到"AI 替你跑腿",程序员的工种正在重写
    34
  • 2
    阿里云百炼大模型服务平台已经接入的主要模型有哪些？调用计费收费标准，新人免费额度介绍
    55
  • 3
    阿里云的云市场购买Qoder后，Qoder授权码在获取？Qoder兑换码如何使用？
    28
  • 4
    Qoder——来自阿里的Agentic 智能体编程平台，Qoder-Teams-Credits费用300元/月，功能及使用场景全解析
    84
  • 5
    使用更少的钱购买到阿里云服务器的方法，亲测省钱购买阿里云指南
    35
  • 6
    Qoder兑换码怎么使用？在阿里云云市场购买的Qoder Teams授权码，兑换码获取及使用教程
    34
  • 7
    阿里云百炼大模型服务平台是什么？最新模型调用收费标准、新人免费额度以及常见问题解答
    99
  • 8
    【开源剪映小助手】遮罩效果接口
    30
  • 9
    从 BI Copilot 到业务 Agent：指标服务如何成为统一数据接口？
    31
  • 10
    当 Agent 从模型调用，走向系统工程：OpenAI 和 LangChain 的两种实践
    65

    • 相关电子书

    更多
  • 低代码开发师（初级）实战教程
  • 冬季实战营第三期：MySQL数据库进阶实战
  • 阿里巴巴DevOps 最佳实践手册
    • 下一篇
    [网络安全] Dirsearch 工具的安装、使用详细教程