{"entities":{"Q6551699":{"pageid":14162854,"ns":120,"title":"Item:Q6551699","lastrevid":103527026,"modified":"2026-06-06T07:33:06Z","type":"item","id":"Q6551699","labels":{"en":{"language":"en","value":"Splitting NP-complete sets infinitely"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7861403"}},"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":"Q6551699$A0B53A86-9A10-415A-AD28-4685BA7EC64B","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"c23e300afced10aaffe7a2625f36f1a62ab77f06","datavalue":{"value":{"text":"Splitting NP-complete sets infinitely","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q6551699$D6EF6EEF-4D85-43CD-9598-2EF00965C1F6","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"e97a8df5396c7aacfa6f64f181f247084aa196c4","datavalue":{"value":"1548.68093","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6551699$9A7B78C8-9D7C-4872-8FE6-A8611D97816D","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"c67fd69af6c91517aae24d4f85769ddfc8b025e8","datavalue":{"value":{"entity-type":"item","numeric-id":652626,"id":"Q652626"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6551699$E60B0659-AABB-40F0-A504-8AF16CBD59F1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"25c7ea4331686681caee9e7368ec272c2a4a0d0a","datavalue":{"value":{"entity-type":"item","numeric-id":1790969,"id":"Q1790969"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6551699$A4DA3FA5-0B4D-4F3F-888D-CE917EF62A14","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"58dc3db180b36df5dd9725e3392cf48200c698af","datavalue":{"value":{"entity-type":"item","numeric-id":1790971,"id":"Q1790971"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6551699$5716CE86-3941-4381-8657-636300740AA8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"9d0db5fe6dbfe4170216f27c1433b7149144e90d","datavalue":{"value":{"entity-type":"item","numeric-id":1790970,"id":"Q1790970"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6551699$D14BF483-8B29-45D3-A8FB-428C4E1CE44A","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"52fa7d44b58d0511cb8993765bd916aef86052d8","datavalue":{"value":{"entity-type":"item","numeric-id":63092,"id":"Q63092"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6551699$8D8C7509-E2EB-4A01-A158-0E2B25BAC47C","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"9f4ebbfebbde9e44ce8411984988976e62e4323a","datavalue":{"value":{"time":"+2024-06-07T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q6551699$CA1559BC-B45C-4CF8-96FC-A0CE2D954A8A","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"15b676bf2261539c6f55a2da0a9d441d3c9a2b4b","datavalue":{"value":"In [Theor. Comput. Sci. 410, No. 21--23, 2011--2023 (2009; Zbl 1191.68333); SIAM J. Comput. 37, No. 5, 1517--1535 (2008; Zbl 1151.68024)] \\textit{C. Gla\u00dfer} et al. proved that, with respect to the many-one reduction, an NP-complete language can be partitioned into two NP-complete languages, and obviously this result is extended to partitions consisting of finitely many NP-complete languages. In the current paper it is proved that this result may be extended to recursive partitions consisting of infinitely many NP-complete languages. The provided proof is rather technical. The authors consider two signals, Rej, for reject, and Acc, for accept. A reduction of a language \\(A\\) into a language \\(B\\) is a map \\(\\phi\\) such that \\(\\phi(A)\\subset B\\cup\\{\\mbox{Acc}\\}\\) and \\(\\phi(A^c)\\subset B^c\\cup\\{\\mbox{Rej}\\}\\), which is equivalent to the conventional definition whenever \\(A\\) is non-trivial, namely when neither \\(A\\) nor \\(A^c\\) are monads. Two languages are equivalent under a reduction if each of them is reducible to the other. It is recalled that any autoreducible language is mitotic: it can be split into two dijoint languages equivalent under reduction to the whole language. A splitting map for a language is valued in \\(\\{0,1\\}\\cup\\{\\mbox{Rej},\\mbox{Acc}\\}\\), takes the value Acc only for words in the language and takes the value Rej only for words in the complement of the language. A flipping map for a splitting map is an autoreduction that switches values in \\(\\{0,1\\}\\). Then it is shown that if there is a splitting function with a corresponding flipping map and these are polynomial-time computable then the language is mitotic. The authors state sufficient conditions, in terms of membership proofs of a language, for a language to be autoreducible, and thereafter explain how to obtain polynomial-time computable splitting functions and corresponding flipping maps. It is proved that any NP-complete language satisfies these conditions. An argument by induction serves to prove the main result in the paper.","type":"string"},"datatype":"string"},"type":"statement","id":"Q6551699$3735CBE1-693F-4EF1-92D8-51EBAEA7410B","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"2c051c55f89b8148a4dc64dba4569555d5561281","datavalue":{"value":{"entity-type":"item","numeric-id":590981,"id":"Q590981"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6551699$891E7B76-367F-4637-9041-8BD238FDE27D","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b4346faa01bb5fb0576370374d6456afd58d5666","datavalue":{"value":"68Q15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6551699$7EB2DDBC-B05E-4DC5-93FB-73FC1BDD0374","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d7656d1c841701431b0b3d99d23720089a267cbb","datavalue":{"value":"03D15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6551699$E5D8088C-4109-454F-9C57-D78AD3F04784","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"6973fe1d554f67e61e6bd5e52f355d166ad01836","datavalue":{"value":"7861403","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6551699$62CD6FB7-9D43-4127-AB78-B3F4ED9C6ED9","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b03b9482d9fb5a4dccce7e9ae84fc4c0475ab15e","datavalue":{"value":"many-one reduction","type":"string"},"datatype":"string"},"type":"statement","id":"Q6551699$DD52D0FD-C8AE-4D42-8127-644A72BA502A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"71d36f6fcc92e00ee58de7dd4fffb159463f3c14","datavalue":{"value":"auto-reducible languages","type":"string"},"datatype":"string"},"type":"statement","id":"Q6551699$37E875BB-DF18-4492-BF73-40BD6685E83A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bb88b1eaf49200e34ef13bbed9924c4508ac3c6a","datavalue":{"value":"splitting NP-complete languages","type":"string"},"datatype":"string"},"type":"statement","id":"Q6551699$665E40BC-E6C5-44EF-A828-B1EDA65C4A42","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":"Q6551699$091774B2-4315-4A73-BF1C-6D17FE0EBDCD","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"23a943f465ac7e7f148f24f1cf760b1107e02f55","datavalue":{"value":{"entity-type":"item","numeric-id":4943880,"id":"Q4943880"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6551699$7A011486-A361-4002-9230-A353E26253B6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6f4242239fc3744329e97417db33fa44816f5299","datavalue":{"value":{"entity-type":"item","numeric-id":4388890,"id":"Q4388890"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6551699$6A12B099-073B-4562-BDD7-46F35FB045A3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2ce7e0ab8a93f0d8bd6a90e08f2465c5e5989293","datavalue":{"value":{"entity-type":"item","numeric-id":3396548,"id":"Q3396548"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6551699$DE2E517E-C83B-4EB1-AF31-AA9F2C38676B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ff678ffdcd55954692548955bd311a2ee30cd595","datavalue":{"value":{"entity-type":"item","numeric-id":1019177,"id":"Q1019177"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6551699$D9CCA6B4-6BA2-40D7-B852-682285CF0F65","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f7c54f781fde158afc699a7a2181753d7238c210","datavalue":{"value":{"entity-type":"item","numeric-id":2973718,"id":"Q2973718"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6551699$7C238954-6DDD-4872-9F5A-CD33FA13EA47","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"beaf354bfb2deec82d355c3fbbd1e476c643a7d3","datavalue":{"value":{"entity-type":"item","numeric-id":881593,"id":"Q881593"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6551699$A81A6731-CBC9-4D54-B230-04FFE61DEC79","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7d8ff4cbdbba49e00cb7d7c110882f49c9046827","datavalue":{"value":{"entity-type":"item","numeric-id":3532575,"id":"Q3532575"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6551699$1128B539-22DA-41CC-A6C9-8F0D67BA59FF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c2a0b468127c3522c5545f19cc6264b526a1e055","datavalue":{"value":{"entity-type":"item","numeric-id":5925718,"id":"Q5925718"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6551699$8903102E-8F3A-471F-B2B2-1B210963A274","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cf83773d8fa1e6a05c7b10cc7c8720647c5b6ecb","datavalue":{"value":{"entity-type":"item","numeric-id":640476,"id":"Q640476"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6551699$6AF83796-366E-4F9F-8EB4-5E4B2E36C6A3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ba48c6dd75052862185f5069e893f6b665add1de","datavalue":{"value":{"entity-type":"item","numeric-id":3978778,"id":"Q3978778"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6551699$C631F4E5-DE54-41AE-9B43-9B813719416E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fb38f485abcaf4c3985ca7a05f2f3c8b60225128","datavalue":{"value":{"entity-type":"item","numeric-id":5918833,"id":"Q5918833"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6551699$8A766214-5400-4D34-8400-DC71BF91C3FB","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"2c6c7387a38e9766cba638b5661925008f5768e1","datavalue":{"value":"10.1016/J.IPL.2024.106472","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6551699$958022EB-1440-4BC8-8D97-6BF4DBF6D880","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"093885727bf20d84d31d39b009ec250045934e3d","datavalue":{"value":{"entity-type":"item","numeric-id":3532575,"id":"Q3532575"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3b1ed4a90a26368d3742e28f2d8b8617b9b44d23","datavalue":{"value":{"amount":"+0.8435324430465698","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":"Q6551699$17321383-7D0C-464D-95F9-51C57776999D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2abceadb66a2925d99ad16d1e4f70930b5b929a4","datavalue":{"value":{"entity-type":"item","numeric-id":5898860,"id":"Q5898860"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"948f1608743d55402f6585fcb5ca28453cb68429","datavalue":{"value":{"amount":"+0.7982304692268372","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":"Q6551699$07CB5C4E-1632-48A1-BAB3-EE99DD83820D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"36a7798eb9bdc7dc71a0347f25008e2cd504102a","datavalue":{"value":{"entity-type":"item","numeric-id":4281519,"id":"Q4281519"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d53bda9d4bbc09c76f94933a6de5dd0b39351ba9","datavalue":{"value":{"amount":"+0.780228316783905","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":"Q6551699$3F036CF7-823E-4693-A9DE-CE366F6AD335","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0adab2ca3c8d782e8977c4ad7f7c6912a446475e","datavalue":{"value":{"entity-type":"item","numeric-id":4388890,"id":"Q4388890"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7f6f31759cdd7cda2e4a3eb14db59b790e1948ad","datavalue":{"value":{"amount":"+0.7554274201393127","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":"Q6551699$B4A46A52-F762-4885-BD7A-B2F7E834243D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"320621171e133588d87511aa1cd507c95947f700","datavalue":{"value":{"entity-type":"item","numeric-id":3813804,"id":"Q3813804"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b20ef2de16be43a8d0626b191daa7b63ae43b0e3","datavalue":{"value":{"amount":"+0.7549335360527039","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":"Q6551699$4D92D01A-1CE9-48E7-B625-80894A1ED83D","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Splitting NP-complete sets infinitely","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Splitting_NP-complete_sets_infinitely"}}}}}