论文标题
用于证明NP问题之间降低的正确性的图形转换方法
A Graph-Transformational Approach for Proving the Correctness of Reductions between NP-Problems
论文作者
论文摘要
决策问题的复杂性NP可以在多项式时间内无确定性解决的决策问题，这是理论上和实用的重要性，而NP问题之间多项式时间减少的概念是NP研究的关键概念。由于许多典型的NP问题自然被描述为图形问题，因此它们及其减少是明显的候选者，可以通过图形转换手段进行研究。在本文中，我们提出了这种图形转换方法，以证明NP问题之间的减少的正确性。
The complexity class NP of decision problems that can be solved nondeterministically in polynomial time is of great theoretical and practical importance where the notion of polynomial-time reductions between NP-problems is a key concept for the study of NP. As many typical NP-problems are naturally described as graph problems, they and their reductions are obvious candidates to be investigated by graph-transformational means. In this paper, we propose such a graph-transformational approach for proving the correctness of reductions between NP-problems.
