并行概率算法与可学习性理论

我们对适合并行处理的一些拓扑结构开展了一系列研究，不仅从图论上而且在算法方面获得了一些成果，如Pancake图、Star图和Arrangement图的直径、容错性、排序算法等多次参加平行算法方面的国际会议，这些成果得到了国内外同行的好评。如何定义NP最优问题的归约及其合理的分类是计算复杂性的重要问题，我们在COCOON'95会议上发表的论文中提出的WL归约及共分类促进了这方面的发展。在机器学习方面，我们对某些具体情况下的样例可学习性获得了一些结果，我们下一步将引入概率因素，设计并行概率算法，提供某些具体的NP最优问题的多项式时间的近似解法，并希望能够从理论上对NP最优问题的平均复杂性有所探讨。