{"entities":{"Q418733":{"pageid":420500,"ns":120,"title":"Item:Q418733","lastrevid":51476153,"modified":"2026-01-18T10:39:07Z","type":"item","id":"Q418733","labels":{"en":{"language":"en","value":"\\textsc{Inverse Hamiltonian cycle} and inverse \\textsc{3Dimensional matching} are coNP-complete"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6039143"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q418733$D5D6D181-A7C7-4A73-81E9-32E18A6C8A3D","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"6dd4e198617ef48e81ec6aad124a23d96de52882","datavalue":{"value":{"text":"\\textsc{Inverse Hamiltonian cycle} and inverse \\textsc{3Dimensional matching} are coNP-complete","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q418733$5870012F-8F99-4DAA-83AD-7FECEB094353","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"8c0b8974de42153428da662a2f4c7aef4ebb5ec9","datavalue":{"value":"1246.68124","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q418733$3DE8EDCC-6F88-42D0-A3D0-7A9C55A8CA2D","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"79831472ed4df992703c82fca0e4a947d0fd8356","datavalue":{"value":{"entity-type":"item","numeric-id":418731,"id":"Q418731"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q418733$1E2B936C-7308-4320-91DC-5694B61D6FAE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"5b4953e0c3613ba7e88878f4e632e6b2dcc9bc49","datavalue":{"value":{"entity-type":"item","numeric-id":418732,"id":"Q418732"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q418733$8B1CDA2E-AA31-4B46-B0F3-A25B4E1E097C","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f3c424cd94a60f9664f9fb69cc6027e75cc7ff3f","datavalue":{"value":{"entity-type":"item","numeric-id":123643,"id":"Q123643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q418733$80180BAA-CF83-48D1-8B61-BFF87A47C87C","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"9cf2f505c732bca65c95db37822678ba6da7d9b6","datavalue":{"value":{"time":"+2012-05-30T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q418733$41C1B0D9-C8FB-4529-8FA8-313AF429DAAB","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"661d704f939b482113153efdc9df9bddffb40155","datavalue":{"value":"The inverse problems of 3-satisfiability, vertex cover, clique and partition problems have been shown to be coNP-complete by \\textit{D. Kavvadias} and \\textit{M. Sideri} [SIAM J. Comput. 28, No. 1, 152--163 (1998; Zbl 0917.68079)] and \\textit{H. Chen} [Lect. Notes Comput. Sci. 2747, 338--347 (2003; Zbl 1124.68368)]. In this paper it is shown that the inverse problems of Hamiltonian cycle and 3-dimensional matching are also coNP-complete. The proofs of the main theorems use some graph gadgets defined by the authors. This completes the study of inverse problems of the six natural NP-complete problems from [\\textit{M. R. Garey} and \\textit{D. S. Johnson}, Computers and intractability. A guide to the theory of NP-completeness. San Francisco, CA: W. H. Freeman and Company (1979; Zbl 0411.68039)] and answers an open question raised by Chen [loc. cit.]. The coNP-completeness of the inverse problem of Hamiltonian cycle is shown to hold for undirected as well as for directed graphs. In particular, it is proved that inverting the natural verifiers of HC and 3DM is complete for the class coNP.","type":"string"},"datatype":"string"},"type":"statement","id":"Q418733$768DE7D8-5109-4629-83B9-924B9C54A348","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"af6f91027425e6a3e182e3068da26575ef8e093e","datavalue":{"value":{"entity-type":"item","numeric-id":190560,"id":"Q190560"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q418733$8F45417F-74A2-4253-9CCF-956113EF7D83","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q418733$7170252A-FDC0-46E7-9656-C86DE7DF763D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q418733$3D1347A4-8811-40B0-A7AA-713EC126B23F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"eef1b49f4a66afb755b22d7419db9d61ba07415f","datavalue":{"value":"05C45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q418733$AFB7036C-CF4D-4318-83BA-26F1A1C4B8FF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q418733$4A325E84-C0D9-472E-92B9-494D19523441","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q418733$EC659BDD-2E1A-40D0-B164-5D21D00A41AD","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"c4d117167f7394ad770788d5615fa6f5c716b2fb","datavalue":{"value":"6039143","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q418733$808B1ACE-3CC2-41FE-9B2B-77CA888DDA77","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2ba0cc3f7aaac8445724ef309c9eecb57f5a563d","datavalue":{"value":"computational complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q418733$9B5FDF50-C679-4EDF-BCFD-B1D8F5813887","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d7cd7406878e515ba27317b33a84ff4ab5ef5a60","datavalue":{"value":"coNP-completeness","type":"string"},"datatype":"string"},"type":"statement","id":"Q418733$C9090A10-BB74-4084-A51B-89FEE0C45565","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8d44d92211fc596a4bd05c5131ceb17525728e9d","datavalue":{"value":"inverse problems","type":"string"},"datatype":"string"},"type":"statement","id":"Q418733$5E99062C-E4EC-4A2B-B984-779F48482E7D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0612807c22f01764e2b3d07b2bb1c1365e520f64","datavalue":{"value":"Hamiltonian cycle","type":"string"},"datatype":"string"},"type":"statement","id":"Q418733$E5157F8B-166D-4F4E-8979-97479CE2571B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c6924d848f377163cf46afeae4820f5c795cf460","datavalue":{"value":"3-dimensional matching","type":"string"},"datatype":"string"},"type":"statement","id":"Q418733$C3E0E2F9-7F3C-4B40-ABDD-F6B34B3BBF2C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cdd918b2384adf54948fbec3fb777dae93a6b7c6","datavalue":{"value":"graph gadget","type":"string"},"datatype":"string"},"type":"statement","id":"Q418733$3C7C8D76-F3A5-434B-B323-8DCFDEADC973","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q418733$DC4CF4CF-0F8C-4DFC-BB06-BE25AE652F95","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"aa9463b51aac438b6a68177cae1724e6a32b2f4a","datavalue":{"value":"https://doi.org/10.1016/j.tcs.2011.08.020","type":"string"},"datatype":"url"},"type":"statement","id":"Q418733$F1E8BA8A-633B-414D-82B2-B54E1ED94E24","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"1d332c1c8284e9def828e98a028a7a37e95a1a8f","datavalue":{"value":"W2007310587","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q418733$8114B927-EF2E-43CF-9A02-56763BE5E7DD","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"2a441c48679efc9da78f233ea356eb1cb65d3933","datavalue":{"value":{"entity-type":"item","numeric-id":5431320,"id":"Q5431320"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q418733$38A608AD-A7B6-4866-9663-9C0B8309B93B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"836ad2a04f82225da478ca9f694f5cd99360b315","datavalue":{"value":{"entity-type":"item","numeric-id":4198056,"id":"Q4198056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q418733$134DE4DC-86A7-4DE7-BC08-423120EB45F2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"210f4cb1411ae40a8cbe7c89e1ee83c5e9a1a99a","datavalue":{"value":{"entity-type":"item","numeric-id":2575753,"id":"Q2575753"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q418733$404B95A2-3598-444B-A56E-2C59AB36FDA4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0d01cde4b45f5d63140df497af3ef04962916e25","datavalue":{"value":{"entity-type":"item","numeric-id":5459120,"id":"Q5459120"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q418733$C4D79555-FB85-4F9E-B44F-667F8D46551F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b0896d4def91ed8d8e8f48a247a42bdacee30665","datavalue":{"value":{"entity-type":"item","numeric-id":4210141,"id":"Q4210141"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q418733$FAE69BA7-BDE1-448E-9129-D37A9A1103C9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"458ab467d1c5397109a383d0e5c939369d06a212","datavalue":{"value":{"entity-type":"item","numeric-id":3221403,"id":"Q3221403"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q418733$A5CE11FB-9380-49EE-8134-E472C1921977","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"3ecf8fc0844575a2f89537decee3edede4b31528","datavalue":{"value":"10.1016/J.TCS.2011.08.020","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q418733$24AD40EE-5DE1-45B5-B8D4-3238B92BCBD3","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"41f3111ba622040533d7cf3c66ed19b8751a3c70","datavalue":{"value":{"entity-type":"item","numeric-id":5459120,"id":"Q5459120"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"602fedaa254feaf0d01e8ebab69ba0f48d3228fb","datavalue":{"value":{"amount":"+0.9757909774780272","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q418733$A2B1EFEA-AC03-46FF-B821-3A599D08B386","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5a0e1ae8210fb03021578f021fa5f4f2094bdc8b","datavalue":{"value":{"entity-type":"item","numeric-id":5431320,"id":"Q5431320"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5992e94d6fd19f96febc1ca77c624fcaa2fd1d96","datavalue":{"value":{"amount":"+0.7987598776817322","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q418733$9C528116-6F3B-40A4-B496-2423A65F0312","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5388d4194dd3f97490bb9bdd017e0fabeb7125d7","datavalue":{"value":{"entity-type":"item","numeric-id":937196,"id":"Q937196"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d0aafd5a426e0349b14b3eeea690f3d657ddb158","datavalue":{"value":{"amount":"+0.7870336771011353","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q418733$6263C159-BE82-4067-B38B-10ED7FABA14B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d066f96ec8d55d189c19ba338856541f779c34fa","datavalue":{"value":{"entity-type":"item","numeric-id":4210141,"id":"Q4210141"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0740c42f12de0af6628f6f0ed024fad80ad57d11","datavalue":{"value":{"amount":"+0.7502219676971436","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q418733$7EF80193-7E99-424B-9058-00C7AA04E61D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"75934591a1338b237a6b1416f57dd6c41b1b95b8","datavalue":{"value":{"entity-type":"item","numeric-id":5710144,"id":"Q5710144"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"205dfa40a6154dfd68ed0bcdb2121fdd745df20f","datavalue":{"value":{"amount":"+0.7434971332550049","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q418733$31C26CB2-D71D-4F62-A046-F4E41F7DE729","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:418733","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:418733"}}}}}