NP难题与不确定问题之间的关系 [英] Relationship between NP-hard and undecidable problems

问题描述

对于不确定的问题和NP难题之间的关系有些困惑. NP困难问题是不确定问题的子集，还是相同和相等，或者它们是不可比较的?

对于我来说，我一直在和我的朋友争论说，无法解决的问题是NP难题的超集.将会存在一些不是NP难但无法确定的问题.但是我发现这个论点太弱了，有些困惑.是否存在无法确定的NP完全问题? NP hard中是否有任何问题是可以确定的??

一些讨论会很有帮助！谢谢！

解决方案

Undecidable =对于某些输入而言无法解决.不管您给算法多少(有限的)时间，在某些输入上总是错误的.

NP-hard〜=超多项式运行时间(假设P！= NP).那是手工操作，但从本质上讲，NP难于解决，至少与NP中最难解决的问题一样困难.

肯定存在一些难解决的NP问题，这些问题并非不可判定(=可判定). SAT说，任何NP完全问题都是其中之一.

是否存在无法解决NP问题的不确定问题?我不这么认为，但要排除它并不容易-我看不出有一个明显的论点，即必须将SAT减少到所有可能的不确定性问题.可能存在一些不可思议的奇怪问题，这些问题不是很有用.但是标准的无法解决的问题(例如暂停问题)是NP难题.

Am a bit confused about the relationship between undecidable problems and NP hard problems. Whether NP hard problems are a subset of undecidable problems, or are they just the same and equal, or is it that they are not comparable?

For me, I have been arguing with my friends that undecidable problems are a superset to the NP hard problems. There would exist some problems that are not in NP hard but are undecidable. But i am finding this argument to be weak and am confused a bit. Are there NP-complete problems that are undecidable.? is there any problem in NP hard which is decidable.??

Some discussion would be of great help! Thanks!

解决方案

Undecidable = unsolvable for some inputs. No matter how much (finite) time you give your algorithm, it will always be wrong on some input.

NP-hard ~= super-polynomial running time (assuming P != NP). That's hand-wavy, but basically NP-hard means it is at least as hard as the hardest problem in NP.

There are certainly problems that are NP-hard which are not undecidable (= are decidable). Any NP-complete problem would be one of them, say SAT.

Are there undecidable problems which are not NP-hard? I don't think so, but it isn't easy to rule it out - I don't see an obvious argument that there must be a reduction from SAT to all possible undecidable problems. There could be some weird undecidable problems which aren't very useful. But the standard undecidable problems (the halting problem, say) are NP-hard.

这篇关于NP难题与不确定问题之间的关系的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！