有个问I,II,III哪个是P的:
I. m个变量 n个register(n<=m), 给出冲突对集(不能占同一个寄存器的变量对),,求分配
II.一种job-shop问题吧. n个工作n台机器,给出哪个工作哪些机器能做,求能否分配开
I可能也是求能不能分配开吧记不准了. 这个我感觉其实是指派问题
III忘了,印象中是个P问题
还有个数字逻辑的, literal指pi或非pi(i=1,...n). 3-clause是三个liternal之和
给出m个3-clause,问给定一种p1~pn,它们都为真的概率
B. (3/8)^m C. (7/8)^m E. { 3(n+1)(n+2)(n+3)/[8n(n-1)(n-2)] }^m
其它选项我印象中m越大越大,还有m*f(n)的形式[f表示我忘了-.-],我想必然不对