A Graph Transformational View on Reductions in NP

Marcus Ermler, Sabine Kuske, Melanie Luderer, Caroline von Totth

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.

Full Text:

PDF


DOI: http://dx.doi.org/10.14279/tuj.eceasst.61.832

DOI (PDF): http://dx.doi.org/10.14279/tuj.eceasst.61.832.826

Hosted By Universit├Ątsbibliothek TU Berlin.