On the complexity of the G-reconstruction problem

Abstract

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.

Keywords

• complexity
• G-reconstruction
• problem