如何证明 "Tile Cover" 在 NP 中
how to justify that "Tile Cover" is in NP
嗨，我正在学习理论计算机科学考试。而且我在学习过去几年的考试，因为每年的任务设置都非常相似。现在我几乎可以解决所有这些任务，除了一个：总是有一个关于 "p vs. np" 问题的问题。
纬度示例：
我们给出了 "Tile Cover" 问题 说：
我们有一个页面长度为 "big" 的矩形
n x m ∈ N
我们有 k "small" 个矩形 ("tiles") r1, r2, ..., rk
问题是所有 "small" 个矩形是否都适合 "big" 个矩形而不留下任何 space。
现在这个问题有一些任务，我已经对第一个感到绝望 说：
"Justify informal why the 'Tile Cover' problem is in NP"
如何解决这个问题或类似的问题（因为我认为今年不会一样）
回想一下众所周知的复杂性表征 class NP 说 NP 正是由那些问题组成的，给定一个问题实例 I和证书 C(I)，我们可以在多项式时间内验证实例 I 是否有解决方案（使用证书，可以将其视为对算法的提示）。更具体地说，可以将证书视为问题实例的一种解决方案（尽管它比这更通用）。 （可以在 Sanjeev Arora 和 Boaz Barak 的精彩著作中找到形式化此声明的定理证明。）
从而证明一个问题在NP中足以证明，给定一个问题实例的解，我们可以及时验证解的大小和问题的大小的多项式该解决方案确实有效。
对于您的具体情况，如果给定一个矩形 R 和一组 "small" 个矩形 S 以及问题的解决方案，就足以表明—— -R 与来自 S--- 的拼贴的拼贴，然后有一种算法可在多项式时间内验证拼贴是否良好（或有效或您称之为什么）。
我想我们正在为同一个考试而学习。在我看来，TILE COVER 在 NP 中，因为你有 k 个小瓷砖 => 这个问题可以在指数时间内解决（k10=]
嗨，我正在学习理论计算机科学考试。而且我在学习过去几年的考试，因为每年的任务设置都非常相似。现在我几乎可以解决所有这些任务，除了一个：总是有一个关于 "p vs. np" 问题的问题。
纬度示例：
我们给出了 "Tile Cover" 问题 说： 我们有一个页面长度为 "big" 的矩形 n x m ∈ N 我们有 k "small" 个矩形 ("tiles") r1, r2, ..., rk
问题是所有 "small" 个矩形是否都适合 "big" 个矩形而不留下任何 space。
现在这个问题有一些任务，我已经对第一个感到绝望 说：
"Justify informal why the 'Tile Cover' problem is in NP"
如何解决这个问题或类似的问题（因为我认为今年不会一样）
回想一下众所周知的复杂性表征 class NP 说 NP 正是由那些问题组成的，给定一个问题实例 I和证书 C(I)，我们可以在多项式时间内验证实例 I 是否有解决方案（使用证书，可以将其视为对算法的提示）。更具体地说，可以将证书视为问题实例的一种解决方案（尽管它比这更通用）。 （可以在 Sanjeev Arora 和 Boaz Barak 的精彩著作中找到形式化此声明的定理证明。）
从而证明一个问题在NP中足以证明，给定一个问题实例的解，我们可以及时验证解的大小和问题的大小的多项式该解决方案确实有效。
对于您的具体情况，如果给定一个矩形 R 和一组 "small" 个矩形 S 以及问题的解决方案，就足以表明—— -R 与来自 S--- 的拼贴的拼贴，然后有一种算法可在多项式时间内验证拼贴是否良好（或有效或您称之为什么）。
我想我们正在为同一个考试而学习。在我看来，TILE COVER 在 NP 中，因为你有 k 个小瓷砖 => 这个问题可以在指数时间内解决（k10=]