Inverse Hamiltonian Cycle and Inverse 3-D Matching Are coNP-Complete

摘要

In this paper we show that the inverse problems of HAMILTONIAN CYCLE and 3-D MATCHING are coNP complete. This completes the study of inverse problems of the six natural NP-complete problems from and answers an open question from. We classify the inverse complexity of the natural verifier for HAMILTONIAN CYCLE and 3-D MATCHING by showing coNP-completeness of the corresponding inverse problems.