"タイルカバー"がNPにあることを正当化する方法

Question

こんにちは私は理論的なコンピュータサイエンスの試験のための学習です。そして、仕事の設定は毎年非常に似ているので、私は最後の年の試験で学習します。そして今、私は1つを除いてこのタスクのほぼすべてを解決することができます： "p対np"問題に関する質問は常に1つあります。

緯度年の例：私たちは、「タイルカバー」問題の魔女を与えている

は言う： 我々は n×m個∈N のページ長との「大」の矩形を持って、我々はKを持っています」 「小さな」四角形がすべて「大きな」矩形に隙間なく収まるかどうかが質問されます。

そして今THERは、この問題のためにいくつかのタスクであり、私はすでに最初の魔女に絶望は言う：

これを解決する方法

「を 『タイルカバー』問題はNPである理由非公式揃え」問題、またはそれに類するもの（今年は同じではないと思うから）

Answer 1

複雑さクラスNPのよく知られた特徴付けでは、正確には次のような問題があります。問題インスタンスIとcertif C(I)では、インスタンスIに（証明書を使用して、アルゴリズムのヒントと考えることができる）解決策があることを多項式時間で検証できます。より具体的には、証明書を問題インスタンスの解決策と考えることができます（それよりも一般的ですが）。 （この主張を定式化した定理の証明は、Sanjeev AroraとBoaz Barakの素晴らしい本で見つけることができます）

したがって、問題がNPにあることを示すには、問題インスタンス時間の経過とともに多項式の解の大きさと解の大きさを検証することができます。あなたの特定のケースについては

、それは我々が長方形Rと「小さな」の長方形Sのセット、および問題の解決策--- SからのタイルとRのタイリングを与えられている場合ことを示せばよいです - - では、タイルが多項式時間で良い（または有効なものであれ何でもよい）ことを検証するアルゴリズムがあります。

Answer 2

私たちは同じ試験のために勉強していると思います。私の考えでは、タイルカバーはNPの中にあります。なぜならあなたは小さなタイルを持っているからです;>問題はexpotential time（k！）で解決できます。