电子科技大学-2018.6月计算复杂性考试

计算复杂性老师：程伟（考试内容是我考试下来大概记下来的，选择题和填空题记不太清楚）一、选择题（单选或多选15分，每小题3分）1.以下哪些问题是P类问题：A、PATHB、HAMPATHC、互质问题D、合数问题2.以下哪些问题是NP类问题：A、PATHB、HAMPATHC、互质问题D、合数问题3.以下哪些问题是NPC问题：A.团问题B.3SAT问题C.独立集问题D.HAMPATH4.以下哪些是PSPACE问题：记不清了5.记不清了二、填空题（15分一空1分）1.屠呦呦获得了（诺贝尔生理学或医学）奖。2.计算机界的诺贝尔奖是（图灵奖）。3.‘我国唯一获得图灵奖的是（姚期智？）院士。’4.然后下面是两个排序题，时间复杂性排序。P,NP,PSPACENPSPACEEXP排序PLNLcoNLEXPPSPACE（这个排序具体记不清了）二、简答题（20分，一题4分）1.M是在所有位置都停止的确定性图灵机，请写出M的时间复杂度的定义。2.M是在所有位置都停止的确定性图灵机，请写出M的空间复杂度的定义。3.写出P类和NP类问题的定义。4.写出一个语言是NP完全的定义5.写出一个语言是PSPACE完全的定义四、计算题（10分）设计一个图灵机来验证该语言是否是A语言，并给出时间复杂性。这题PPT上面有。五、证明题（40分，每个题10分）1.A≤pB,B∈P证明A∈P证明：A可以多项式次数调用多项式时间的算法来完成，所以A可以在多项式时间内完成2.B是NPC问题，B∈P证明P=NP证明：设A是任意一个NP类问题，由NPC定义可知A≤pB又因为B∈P所以A可以多项式时间调用一个多项式算法来完成。所以A∈P因为A作为NP问题具有任意性。所以NP是P的子集又因为P是NP的子集所以NP=P3.B是NPC问题，B≤pC证明C是NPC问题。证明：设A是任意一个NP类问题，由NPC定义可知A≤pB又因为B≤pC所以A≤pC即任意一个NP问题都可以多项式时间内规约到C问题。所以C是NPC问题。4.证明3SAT问题可以多项式时间规约到CLIQUE问题。证明的时候首先构建映射然后再证明该映射的正确性。