On the complexity of graph reconstruction

In the wake of the resolution of the four-color conjecture, the graph reconstruction conjecture has emerged as one focal point of graph theory. This paper considers thecomputational complexity of decision problems (Deck Checking andLegitimate Deck), construction problems (Preimage Construction), and counting problems (Preimage Counting) related to the graph reconstruction conjecture. We show that:1.$${\text{GRAPH}} {\text{ISOMORPHISM}} \leqslant _m^l LEGITIMATE DECK, and$$2$${\text{GRAPH}} {\text{ISOMORPHISM}} \equiv _{iso}^l DECK CHECKING.$$