如何证明一个问题是NP难。

[复制链接]

字体大小: 正常放大

winning3

2 主题	4 听众	120 积分

升级 10%

TA的每日心情

	开心 2012-10-25 12:36

签到天数: 1 天

[LV.1]初来乍到

电梯直达

1^#

发表于 2009-7-7 16:17 |只看该作者 |倒序浏览

|招呼Ta 关注Ta

1．
某旅馆有一间会议厅，顾客可以预先预定使用该会议厅的天数。证明：若至少有一人要求使用该会议厅的时间是确定的，且分配给预定者使用该会议厅的时间期限是有上界的（即只制定规定天数的使用计划），则管理员要确定是否可以不拒绝顾客的问题是NP难的（解：设有n个顾客各预订了a1,…,an天，∑ai = 2B ，D = 2B +1, 另有一人预定在t = B 时使用1天，确定是否要拒绝顾客等价于划分问题）

zan