MSP问题相关论文
摘 要：针对一个NP完全问题，即MSP问题，研究其问题的结构性质，猜想特殊的结构可以使其算法证明得到简化。以简化证明为导引，提出一种特殊......
自从Steve Cook证明了第一个NP完全问题以来,大量的NP完全问题不断被发现,而且很多问题具有重要的实际应用。比如,SAT问题是大规模......
P vs.NP问题一直是理论计算机科学领域中最为复杂的一个问题,已经被列为世界七大数学难题之首。P vs.NP问题已经吸引了世界上许多......
提出多级图简单路径求解问题,我们称之为MSP问题.给出求解该问题的Z-H算法,证明算法的正确性,分析算法的时间复杂性.最后通过将HC......
针对文献[1]中提出的MSP问题（定义见正文）,从SAT问题出发,给出SAT问题到MSP问题的多项式归结,进而给出MSP问题NP完全性质的另一种证......
针对文献[1,2]提出的MSP问题,研究了MSP问题与着色问题、子图同构问题的对应关系,揭示了MSP问题所反映的NP完全问题的共性;分析了M......
文献[1]提出的MSP问题是一个NP完全问题。为了求解MSP问题，文献[1]给出了ZH算法。本文以ZH算法为研究对象，剖析ZH算法主要过程，从新的......
摘要：提出多级图简单路径求解问题，我们称之为MSP问题。给出求解该问题的Z－H算法，证明算法的正确性，分析算法的时间复杂性。最后通过将H......
NP=?P(即NP是否等于P)的问题是计算机科学和数学中的重要问题。美国克雷数学研究院将其列为新千年七大困难问题之首,2005年Science......
MSP问题是文献[1,2]提出的一个问题。研究表明[3]该问题对NP类问题有很强的表达能力。本文给出一个关于该问题的求解算法、复杂性......
