Np硬度低下

問題がnp-hardであることを示したい場合は、既存のnp-hard問題を複数回使用するのは問題ありませんか？たとえば、ハミルトニアンサイクルをグラフでn回使用します（nは頂点の数です）。あるいは、グラフを1回使用された既存のnp-hard問題で簡単に解決できるものに変換する必要がありますか？Np硬度低下

出典

2012-01-09 Mads Andersen

@PeteKirkham：cstheoryは研究レベルの質問です。この質問は、cstheoryの話題とは異なりますので、閉じられます。 – amit

正確な口座を表示する必要があります。

NP-Hardの問題で問題を解決できることがわかっても、何も証明されません。 [あなたはSATを使ってNPのすべての問題を解決することができます。Cook-Levin Theorem]。

問題が多項式時間で解けるなら、NP困難な問題があることを示しておく必要があります。それが実際に削減されたもの。

例：TSPを使用してshortest pathを解決することができます。最短経路はNP-Hardですか？もちろん違います！それは、TSPが少なくとも最短経路と同じくらい難しいことを示しているだけです！

出典

2012-01-09 13:40:31 amit

これは私の質問に答えたと思います。私は既知のNP-Hard問題によって解決できるように、問題を（多項式時間で）変換する必要があります。これはまた、私が最初の質問に答えるためにNP-Hardの既知の問題を1回だけ使うべきことを意味します。 –

@MadsAndersen：いいえ。あなたは** NP困難な問題をあなたの問題**に変換して**それがNP困難であることを示す必要があります。言い換えれば、問題のアルゴリズムを使ってNP-Hardの問題を解決してください。それが多項式時間で行うことができれば - あなたの問題はNP-Hardです。 – amit

ありがとうたくさん - 助けて！ –

私は数学者ではありませんが、問題の問題が少なくとも既存のNP困難な問題、またはその倍数であることを証明できれば十分です証明？ヒョウの皮を剥ぐことが2匹の猫をスキンするよりも複雑である場合、1匹の猫を皮をむくよりも複雑であるということは常識的なことです。

出典

2012-01-09 13:36:48

これは意味がありません。 TSPを使って2頂点間の最短距離を解くことができれば、最短パスはNP-Hardですか？ – amit

私はその表紙を一人でよく残しておきます - 私が言ったように、私は数学者ではありません。私は、もしあなたがそれが「少なくとも複雑で、解決できない」と証明できるなら、あなたは私をちょっと誤解していないと確信していますか？ –

少なくとも質問には答えません。質問に重大な論理障害があります。それを言及していないすべての答えは基本的に間違っています。 – amit

ニューヨークからパリへの移動は、そのパスが最短であることを証明しません。

出典

2012-01-09 14:10:41 xyz

答えて

関連する問題