A Graph Transformational View on Reductions in NP

Abstract

Many decision problems in the famous and challenging complexity class NP are graph problems and can be adequately specified by polynomial graph transformation units. In this paper, we propose to model the reductions in NP by means of a special type of polynomial graph transformation units, too. Moreover, we present some first ideas how the semantic requirements of reductions including their correctness can be proved in a systematic way.