blocks|key|4584522|text|要回答这个问题，首先需要了解哪些NP-hard问题也是NP-完全问题。如果一个NP-hard问题属于集合NP，则它是NP-完全问题。要属于集合NP，问题需要是|type|unstyled|depth|inlineStyleRanges|entityRanges|data|4584523|(i)决策问题，|4584524|(ii)问题的解的数目应该是有限的，并且每个解的长度应该是多项式的，以及|4584525|(iii)给定一个多项式长度的解，我们应该能够说出问题的答案是否是是/否|4584526|现在，很容易看出，可能存在许多不属于集合NP且更难解决的NP-hard问题。作为一个直观的例子，优化版本的旅行推销员，我们需要找到一个实际的时间表比决策版本的旅行推销员，我们只需要确定是否存在长度为<=+k的时间表。|4584527|entityMap^0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|L|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|M|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|N|8|@]|9|@]|A|$]]|$1|F|3|G|5|6|7|O|8|@]|9|@]|A|$]]|$1|H|3|I|5|6|7|P|8|@]|9|@]|A|$]]|$1|J|3|-4|5|6|7|Q|8|@]|9|@]|A|$]]]|K|$]]

To answer this question, you first need to understand which NP-hard problems are also NP-complete. If an NP-hard problem belongs to set NP, then it is NP-complete. To belong to set NP, a problem needs to be

(i) a decision problem, 
(ii) the number of solutions to the problem should be finite and each solution should be of polynomial length, and 
(iii) given a polynomial length solution, we should be able to say whether the answer to the problem is yes/no

Now, it is easy to see that there could be many NP-hard problems that do not belong to set NP and are harder to solve. As an intuitive example, the optimization-version of traveling salesman where we need to find an actual schedule is harder than the decision-version of traveling salesman where we just need to determine whether a schedule with length &lt;= k exists or not.

blocks|key|1853256|text|图灵机停机问题在图灵机和NP-hard上是不可判定的，但不是NP-hard。显然，它更难;)|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1853257|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|D|8|@]|9|@]|A|$]]|$1|B|3|-4|5|6|7|E|8|@]|9|@]|A|$]]]|C|$]]

Turing machine halting problem is undecidable on Turing machines and NP-hard, but not NPC. Apparently it is harder ;)

blocks|key|4584495|text|NP-hard问题集是NP-完全问题集的超集。有一些比NP更“难”的复杂类，例如PSPACE、EXPTIME或EXPSPACE，所有这些都包含NP-hard但不是NP-complete问题。|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|4584496|entityMap|0|LINK|mutability|MUTABLE|url|http://en.wikipedia.org/wiki/PSPACE|1|http://en.wikipedia.org/wiki/EXPTIME|2|http://en.wikipedia.org/wiki/EXPSPACE^0|14|6|0|1B|7|1|1J|8|2|0^^$0|@$1|2|3|4|5|6|7|P|8|@]|9|@$A|Q|B|R|1|S]|$A|T|B|U|1|V]|$A|W|B|X|1|Y]]|C|$]]|$1|D|3|-4|5|6|7|Z|8|@]|9|@]|C|$]]]|E|$F|$5|G|H|I|C|$J|K]]|L|$5|G|H|I|C|$J|M]]|N|$5|G|H|I|C|$J|O]]]]

The set of NP-hard problems is a superset of the set of NP-complete problems. There are complexity classes more "difficult" than NP, for example <a href="http://en.wikipedia.org/wiki/PSPACE" rel="noreferrer">PSPACE</a>, <a href="http://en.wikipedia.org/wiki/EXPTIME" rel="noreferrer">EXPTIME</a> or <a href="http://en.wikipedia.org/wiki/EXPSPACE" rel="noreferrer">EXPSPACE</a>, and all these contain NP-hard but not NP-complete problems.

blocks|key|4584574|text|图灵停顿问题是一个不可判定的问题，属于NP-Hard集。对于图灵停顿问题，我们没有任何判决器，因为它是一种RE语言。所以我们没有任何算法来解决这个问题。由此可见，不可解问题也是NP-Hard集。因此，NP-Hard集合还包含我们没有任何算法要解决的语言或问题。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|4584575|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|D|8|@]|9|@]|A|$]]|$1|B|3|-4|5|6|7|E|8|@]|9|@]|A|$]]]|C|$]]

Turing halting problem is undecidable and it belongs to NP-Hard set. For turing halting problem we do not have any decider as it is a RE language. So we do not have any algorithm to solve it. Thus it is clear that unsolvable problems are also in NP-Hard set . So NP-Hard set also contains the languages or problems for which we do not have any algorithm to solve.

blocks|key|2473404|text|来自http://en.wikipedia.org/wiki/NP-hard#Examples|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|2473405|2473406|还有一些决策问题是NP难的，但不是NP完全的，例如停顿问题。这就是一个问题：“给定一个程序及其输入，它会永远运行吗？”这是一个是/否的问题，所以这是一个决策问题。很容易证明停工问题是NP难的，但不是NP完全的。|blockquote|2473407|2473408|entityMap|0|LINK|mutability|MUTABLE|url|http://en.wikipedia.org/wiki/NP-hard#Examples^0|2|19|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|Q|8|@]|9|@$A|R|B|S|1|T]]|C|$]]|$1|D|3|-4|5|6|7|U|8|@]|9|@]|C|$]]|$1|E|3|F|5|G|7|V|8|@]|9|@]|C|$]]|$1|H|3|-4|5|6|7|W|8|@]|9|@]|C|$]]|$1|I|3|-4|5|6|7|X|8|@]|9|@]|C|$]]]|J|$K|$5|L|M|N|C|$O|P]]]]

From <a href="http://en.wikipedia.org/wiki/NP-hard#Examples" rel="nofollow">http://en.wikipedia.org/wiki/NP-hard#Examples</a>

<blockquote>
 There are also decision problems that are NP-hard but not NP-complete, for example the halting problem. This is the problem which asks "given a program and its input, will it run forever?" That's a yes/no question, so this is a decision problem. It is easy to prove that the halting problem is NP-hard but not NP-complete.
</blockquote>

blocks|key|6001393|text|type|unstyled|depth|inlineStyleRanges|entityRanges|data|6001394|+NP+-complete必须是NP且NP-hard。非NP完全的|ordered-list-item|6001395|和NP-hard不是NP。|6001396|现在，根据NP的定义，有人给出了问题的答案实例。还有验证器需要验证。|6001397|这意味着NP-Hard没有它们中的任何一个。因此它们很难解决是真的。|6001398|6001399|entityMap^0|0|0|0|0|0|0^^$0|@$1|2|3|-4|4|5|6|M|7|@]|8|@]|9|$]]|$1|A|3|B|4|C|6|N|7|@]|8|@]|9|$]]|$1|D|3|E|4|C|6|O|7|@]|8|@]|9|$]]|$1|F|3|G|4|C|6|P|7|@]|8|@]|9|$]]|$1|H|3|I|4|C|6|Q|7|@]|8|@]|9|$]]|$1|J|3|-4|4|5|6|R|7|@]|8|@]|9|$]]|$1|K|3|-4|4|5|6|S|7|@]|8|@]|9|$]]]|L|$]]

<ol>
<li>NP-complete must be NP and NP-hard. </li>
<li>and NP-hard which are not NP-complete are not NP.</li>
<li>Now by definition of NP there is someone who give answer instance for problem. and there is verifier to verify.</li>
<li>this means NP-Hard does not have either one of them. Hence they are difficult to solve is True. </li>
</ol>

From my understanding, all NP-complete problems are NP-hard but some NP-hard problems are known not to be NP-complete, and NP-hard problems are at least as hard as NP-complete problems.

Is that mean NP-hard problems that are not NP-complete are harder? And how it is harder?

NP-hard problems that are not NP-complete are harder?

翻译质量差，导致语言生硬或混乱。

没有提供实际的解决方法或示例。

解答不清晰，无法理解或解决问题。

页面排版不美观，阅读体验差。

文章

问答

视频

教程

学习中心

腾讯云实验室

直播

竞赛

腾讯云代码分析专区

腾讯iOA零信任安全管理系统专区

腾讯云架构师技术同盟交流圈

腾讯云数据库专区

腾讯云智能顾问专区

腾讯云原生专区

腾讯混元专区

腾讯云TCE专区

腾讯云Lighthouse专区

腾讯云HAI专区

腾讯云Edgeone专区

腾讯云存储专区

腾讯云智能专区

腾讯轻联专区 

腾讯云开发专区

TAPD专区

腾讯轻量云游戏服专区

腾讯云最具价值专家

腾讯云架构师技术同盟

腾讯云创作之星

腾讯云开发者先锋

腾讯云AI代码助手

云原生构建

TAPD 敏捷项目管理

Cloud Studio

SDK中心

API中心

命令行工具

功能1上新10个字符

功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符。

功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符。

功能5描述100个字符功能5描述100个字符功能5描述100个字符功能5描述100个字符功能5描述100个字符功能5描述100个字符

功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符

功能4上新

文章&问答评论现已支持表情

全新交互，全新视觉，新增快捷键、悬浮工具栏、高亮块等功能并同时优化现有功能，全面提升创作效率和体验

社区富文本编辑器全新改版！诚邀体验～ 

精选全网热门MCP server，让你的AI更好用 🚀

💥开发者 MCP广场重磅上线！

涵盖代码开发、场景应用、自动测试全流程，助你从零构建专属AI助手

一站式MCP教程库，解锁AI应用新玩法

聚焦“写作效率、视觉美观与运行性能”三方面进行全面升级，为您提供更高效、稳定的创作环境

社区富文本&Markdown编辑器全新改版上线，欢迎大家体验!

诚挚邀请您参与本次调研，分享您的真实使用感受与建议。您的反馈至关重要，感谢您的支持与参与！

社区新版编辑器体验调研

据我所知，所有的NP-完全问题都是NP-难的，但有些NP-hard问题不是NP-完全的，并且NP-hard问题至少和NP-完全问题一样难。这是不是意味着不是NP完全的NP-hard问题更难？以及它如何变得更难？

问不是NP-完全的NP-hard问题更难？
EN

回答 6

Stack Overflow用户

Stack Overflow用户

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问不是NP-完全的NP-hard问题更难？EN

回答 6

Stack Overflow用户

Stack Overflow用户

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问不是NP-完全的NP-hard问题更难？
EN