Research Space for Linear Algebra & Discrete Mathematics
1. 大部分的人都猜測NP-complete的問題確實沒有subexponential的演算法可以解, 但這到目前為止都還沒有被證明, 所以我們還不能肯定的說這個命題一定是對的2. connectivity就是問只少要去到幾個點才會導致graph不連通, edge connectivity意思也差不多, 不過是改成去掉的最少邊數NP-complete我覺得其實考試會問的都不會太難, 一類是考觀念, 只要把P,NP,NP-complete,NP-hard之間的關係弄清楚, 像是什麼是polynomial time reduction、complete、P!=NP的conjecture等等的觀念, 就沒什麼問題了; 演算法裡通常會考的另一類則是要你證明一個問題屬於NP-Complete, 通常都是給你一個已知為NPC的問題, 請你給出之間的reduction, 在考試時雖然不見得有時間想的出來, 但常考的reduction也就只有少數幾個而已, 掌握那些應該也就差不多了
感謝~了解
張貼留言
2 則留言:
1. 大部分的人都猜測NP-complete的問題確實沒有subexponential的演算法可以解, 但這到目前為止都還沒有被證明, 所以我們還不能肯定的說這個命題一定是對的
2. connectivity就是問只少要去到幾個點才會導致graph不連通, edge connectivity意思也差不多, 不過是改成去掉的最少邊數
NP-complete我覺得其實考試會問的都不會太難, 一類是考觀念, 只要把P,NP,NP-complete,NP-hard之間的關係弄清楚, 像是什麼是polynomial time reduction、complete、P!=NP的conjecture等等的觀念, 就沒什麼問題了; 演算法裡通常會考的另一類則是要你證明一個問題屬於NP-Complete, 通常都是給你一個已知為NPC的問題, 請你給出之間的reduction, 在考試時雖然不見得有時間想的出來, 但常考的reduction也就只有少數幾個而已, 掌握那些應該也就差不多了
感謝~了解
張貼留言