送交者: steven 于 2006-1-02, 02:22:22:
回答: 请教：如何证明一个关于graph traversal的NP-Complete问题 由 xm1223 于 2005-12-29, 15:15:52:
you can reduce an known NP-complete problem as an instance of your problem. That means if anyone can find a P-time algorithm for your problem, the same algorithm can solve all NP problems. The reduction has to be an algorithm which requires linear bounded memory space and runs in polynomial time. Since you haven't really define your graph traversal problem, I can only give you some general hints.