On the complexity of the G-reconstruction problem

Abstrakt

We investigate the computational complexity of the class of decision problems called G-reconstruction. We prove that these problems are NP-complete for many values of the parameter G.