如何证明 class-room scheduling 问题是 NP 完全正确的？
How do I prove a class-room scheduling issue to be NP complete correctly?
给我一道题，就是在一个学校的k个房间里安排n classes，是一个决策题，因为我们想问能不能安排这n classes 在这 k 个房间中，以便不超过给定的时间限制 t（classes 在某种预定方式中的总时间不应超过 t）。
我知道要首先证明问题的每个解决方案都可以在多项式时间内得到验证，但是当涉及到将一些已知的 NP 完全问题简化为 class-room scheduling 问题时，我会这样做不知道应该考哪个NP完全问题
我正在考虑使用旅行推销员问题来减少，但我不确定如何将我的 class-room scheduling 问题解释为考虑符号的图表。我第一次尝试将我的问题解释为图形是将 classes 视为顶点，将房间视为颜色，将 class 的时间表示为两个 classes 之间的加权边（后两种解释完全不确定）。但我不知道这是否遵循某些调度问题的标准模式，或者我什至不知道旅行商问题是否是一个很好的 NP 完全问题，可以减少到 class-房间调度问题。在后一种情况下，我想知道更合适的 NP 完全问题的例子，以减少我的情况。
提前致谢！
你可以用map-coloring (graph-coloring)。您只需要为边和节点定义规则。节点将是 类，房间将是颜色，并且您不能同时连接 类。这实际上是 k 着色问题，您需要用 k 种颜色为特定图形着色，以尽量减少每种颜色的 类 数量。但是在这种特殊情况下，您只需要小于或等于每种颜色的 t。您可以通过标准的着色规则来实现这一点，并在新颜色达到 类 时立即切换到新颜色。
这仍然是一个NP完全问题。唯一的例外是当你有 1 或 2 类，那么它是多项式时间。当你有 1 个房间时，你只需要检查是否 n<=t。当你有 2 个房间时，你只需要检查它是否可以用 2 种颜色着色。您可以通过 DFS（但首先检查 n <= 2t）和第一种颜色的奇数步和第二种颜色的偶数步来实现这一点。如果可以使用此策略为所有节点着色，那么您就有了一个正解。当k>=3时，它是NP-complete.
给我一道题，就是在一个学校的k个房间里安排n classes，是一个决策题，因为我们想问能不能安排这n classes 在这 k 个房间中，以便不超过给定的时间限制 t（classes 在某种预定方式中的总时间不应超过 t）。
我知道要首先证明问题的每个解决方案都可以在多项式时间内得到验证，但是当涉及到将一些已知的 NP 完全问题简化为 class-room scheduling 问题时，我会这样做不知道应该考哪个NP完全问题
我正在考虑使用旅行推销员问题来减少，但我不确定如何将我的 class-room scheduling 问题解释为考虑符号的图表。我第一次尝试将我的问题解释为图形是将 classes 视为顶点，将房间视为颜色，将 class 的时间表示为两个 classes 之间的加权边（后两种解释完全不确定）。但我不知道这是否遵循某些调度问题的标准模式，或者我什至不知道旅行商问题是否是一个很好的 NP 完全问题，可以减少到 class-房间调度问题。在后一种情况下，我想知道更合适的 NP 完全问题的例子，以减少我的情况。
提前致谢！
你可以用map-coloring (graph-coloring)。您只需要为边和节点定义规则。节点将是 类，房间将是颜色，并且您不能同时连接 类。这实际上是 k 着色问题，您需要用 k 种颜色为特定图形着色，以尽量减少每种颜色的 类 数量。但是在这种特殊情况下，您只需要小于或等于每种颜色的 t。您可以通过标准的着色规则来实现这一点，并在新颜色达到 类 时立即切换到新颜色。
这仍然是一个NP完全问题。唯一的例外是当你有 1 或 2 类，那么它是多项式时间。当你有 1 个房间时，你只需要检查是否 n<=t。当你有 2 个房间时，你只需要检查它是否可以用 2 种颜色着色。您可以通过 DFS（但首先检查 n <= 2t）和第一种颜色的奇数步和第二种颜色的偶数步来实现这一点。如果可以使用此策略为所有节点着色，那么您就有了一个正解。当k>=3时，它是NP-complete.