{"entities":{"Q1097029":{"pageid":1107781,"ns":120,"title":"Item:Q1097029","lastrevid":66682053,"modified":"2026-04-12T11:53:52Z","type":"item","id":"Q1097029","labels":{"en":{"language":"en","value":"A note on complete problems for complexity classes"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4033075"}},"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":"Q1097029$49A14396-4D7C-4D96-A9EE-DECC00194EF7","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"9fbc17e4fee22d98d698ae6b4f576f0a7ecef88f","datavalue":{"value":{"text":"A note on complete problems for complexity classes","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1097029$0833594B-46CD-4948-A27B-9F170A9B1306","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"f186b4eb41363258e7edd3bc0c26984cd60bd455","datavalue":{"value":"0634.68036","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1097029$2D94D538-0D49-4BA7-880B-0779E514F70F","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"acca00bcd1e1a7f39bb8819b513ff60e9f2af2b1","datavalue":{"value":"10.1016/0020-0190(86)90078-5","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1097029$EE1177FD-F561-45EE-AD44-446007F02D1D","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":"Q1097029$1EB3AA49-2ABE-4F2E-A6DD-840DC17468CF","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"63df7153432d81fa42019fcabb076c89649b0b5b","datavalue":{"value":{"time":"+1986-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1097029$B019D1BB-5003-41B1-91DF-1156D012380A","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"e802b17ed0e5f934dd4db991379adb8159f3c51e","datavalue":{"value":"Let \\(\\leq_{pm}\\) and \\(\\leq_{pT}\\) denote the polynomial-time bounded many-one and Turing reducibilities respectively. Clearly, every \\(\\leq_{pm}\\)-complete set for some class will also be \\(\\leq_{pT}\\)- complete for the class. This paper is concerned with determining when a class which has a \\(\\leq_{pT}\\)-complete set also has a \\(\\leq_{pm}\\)- complete set (now not necessarily the same set). Results of Ladner et al. tell us that this is not always the case.    A main construction is presented for obtaining from any recursive set A a new recursive set A * which is polynomial-time bounded Turing equivalent to A (i.e., \\(A\\equiv_{pT}A\\) *) and also satisfies \\(\\forall B\\) \\((B\\leq_{pT}A\\to B\\leq_{pm}A\\) *). This is fairly straightforward and uses a universal oracle machine \\(M_ U(A)\\) which on input 0 n1x computes \\(M_ n(A)(x)\\) in \\(p(p_ n(x))\\) steps for some polynomial p, where \\(M_ n(A)\\) is some standard recursive enumeration of oracle Turing machines with polynomial bounds \\(p_ n.\\)    The main theorem then follows from this construction: For \\({\\mathcal C}^ a \\)class of recursive sets closed under \\(\\equiv_{pT}\\), \\({\\mathcal C}\\) has a \\(\\leq_{pm}\\)-complete set if \\({\\mathcal C}\\) has a \\(\\leq_{pT}\\)-complete set. The proof is simply a matter of checking that if A is \\(\\leq_{pT}\\)- complete for \\({\\mathcal C}\\) then A * is \\(\\leq_{pm}\\)-complete for \\({\\mathcal C}.\\)    Some interesting corollaries which can now be proved are: \\(\\Delta\\) \\(p_ n\\) has \\(\\leq_{pm}\\)-complete sets. The class NP\\(\\cap co\\)-NP has a \\(\\leq_{pm}\\)-complete set iff it has a \\(\\leq_{pT}\\)-complete set. Partial orderings of pm-degrees in \\(\\deg_{pT}(A)\\) have a greatest element for any recursive set A.    All proofs are clearly presented with just the correct amount of detail required.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1097029$EB989D29-3A61-46FF-905F-508244405A45","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1097029$77009096-AC08-4FE6-A3A5-CD72A908A1D8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"4c09ea78484192dfb20180fed0b8ec0fbe50483f","datavalue":{"value":"03D60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1097029$7338FD31-DE92-4BD0-8EE9-745C7FDA0AC6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d7656d1c841701431b0b3d99d23720089a267cbb","datavalue":{"value":"03D15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1097029$B4CA74B1-3F49-4A60-AE19-DA4B4FBC4863","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"d48313f28e6f5a989c1e4df405f1a773e769d428","datavalue":{"value":"4033075","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1097029$B2DDC02B-7005-4BED-B7CF-D98789D92AB1","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7151de391a7de3cec2f7cb00d3da9130d11d1609","datavalue":{"value":"polynomial many-one reductibility","type":"string"},"datatype":"string"},"type":"statement","id":"Q1097029$10A1A389-F18D-439E-B81A-47CFA43EBD2C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0367a7792670419caf93ffd6556bed68de0f0a4d","datavalue":{"value":"polynomial Turing reducibility. recursive set","type":"string"},"datatype":"string"},"type":"statement","id":"Q1097029$AE7981D7-1B3A-4ECD-862D-DCE6936C02EB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"80a9fafab9301c90f58754c8a296c1f5661d40fc","datavalue":{"value":"oracle Turing machines","type":"string"},"datatype":"string"},"type":"statement","id":"Q1097029$13856638-D848-49C0-A10D-E526C0AA3AB7","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"2b09a388965329c926d542d4fdd3e9db9fa7e3d1","datavalue":{"value":{"entity-type":"item","numeric-id":162061,"id":"Q162061"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1097029$B281328C-BA9B-4111-AAF5-94C91F8DC79D","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":"Q1097029$7A913BE5-C60D-4D7B-BE03-50027BDA8204","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"862b13c750c6ae4977987306a07fe6927ceaa63e","datavalue":{"value":"https://doi.org/10.1016/0020-0190(86)90078-5","type":"string"},"datatype":"url"},"type":"statement","id":"Q1097029$8DFC9225-227F-41EC-9084-936C3943AEEF","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"2e73ca1500ab4a11591e89643bf1e10ef7a225e6","datavalue":{"value":"W2064874002","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1097029$8BE2B666-8AFB-4C39-A11D-BAF9F8B73C49","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"03604493ac7e94558c9c3dc4821ea3dafd6be35d","datavalue":{"value":{"entity-type":"item","numeric-id":3698788,"id":"Q3698788"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1097029$8EF68362-0643-435C-ADC8-4F98BD393C87","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ef757ecac8e00102e8fe2d81d7657ee3391ff698","datavalue":{"value":{"entity-type":"item","numeric-id":4138187,"id":"Q4138187"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1097029$E1E5765A-C8A9-4D39-8835-FC213536864C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5e65d73ae8ce50631a13a2e25599a048bc2eda73","datavalue":{"value":{"entity-type":"item","numeric-id":4158479,"id":"Q4158479"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1097029$C3AD0488-11C4-401A-870C-E5F860DD7C0C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"adc67edbb1677ad77489d6c17db913a838f0b011","datavalue":{"value":{"entity-type":"item","numeric-id":3696516,"id":"Q3696516"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1097029$9B1B1A69-14D7-48E1-9ADF-FF26A4B14CF9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2043397a54eaa38033021fac24881dafefacec7d","datavalue":{"value":{"entity-type":"item","numeric-id":5592246,"id":"Q5592246"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1097029$FE4F696C-7D2C-4657-965E-855DCE2380F6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"755b705d434743289f1c33d94607b3327759f7e3","datavalue":{"value":{"entity-type":"item","numeric-id":4142699,"id":"Q4142699"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1097029$46983A2C-124C-40D8-92FA-4230D4AE1F5E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6a2654c1ad3008ab65ddf962a999d4d8045dcdea","datavalue":{"value":{"entity-type":"item","numeric-id":4085242,"id":"Q4085242"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1097029$B09F1245-6786-4D28-AFC8-BB293709EB04","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c7d15acf9b2dc594da15dc289088a8a93d59b4f8","datavalue":{"value":{"entity-type":"item","numeric-id":1223166,"id":"Q1223166"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1097029$C390D61B-214E-45BB-827B-3956269C6E3F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"66d483301320293f55a374a9d87a8df8613bea65","datavalue":{"value":{"entity-type":"item","numeric-id":3942949,"id":"Q3942949"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1097029$37F88A2E-EF22-4E6D-880E-979014120303","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"32c9cf122d104d7332be7d6610d7ce2681b03b64","datavalue":{"value":{"entity-type":"item","numeric-id":3768398,"id":"Q3768398"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1097029$18B78268-F64E-4EB6-A4C4-246F6F78B034","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"37bd93f050a29505d9954e41ab03268b153e49a7","datavalue":{"value":{"entity-type":"item","numeric-id":4190619,"id":"Q4190619"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1097029$7BC2DF05-D4EB-40A2-A049-943F10B2902C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9fb2c936121f4f1d6e6f7ab70089a797e73426bb","datavalue":{"value":{"entity-type":"item","numeric-id":3662618,"id":"Q3662618"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1097029$73B792FC-38F3-47A3-80A3-79194BDC2493","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e4751cb99cfb27abec44f2378f8165a3a9a6376a","datavalue":{"value":{"entity-type":"item","numeric-id":1236109,"id":"Q1236109"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1097029$B27CA78B-A87A-41A0-A447-F640164617F1","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a471061c89390c08444ed3f0ac95f6dac2d7771e","datavalue":{"value":{"entity-type":"item","numeric-id":4712077,"id":"Q4712077"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c51bbb981188111056ebf2567e411b0215497d76","datavalue":{"value":{"amount":"+0.8773271441459656","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":"Q1097029$2F3DABE1-18C5-4CB5-9AD4-7C0D0F0F2478","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7024b584150a2e1ba8672fba00213125bc7194de","datavalue":{"value":{"entity-type":"item","numeric-id":4016403,"id":"Q4016403"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4b83ee1b5fb9c1a9b47609aa09dac250a4ec5f2a","datavalue":{"value":{"amount":"+0.8529598712921143","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":"Q1097029$4306E50F-947B-448D-8010-EA873B796067","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d76690291e93d19d4faadc3c92797917b1d2edc1","datavalue":{"value":{"entity-type":"item","numeric-id":1112017,"id":"Q1112017"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1b258f22f7732eb2d7a804f15660629988d99262","datavalue":{"value":{"amount":"+0.8501408100128174","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":"Q1097029$91A2EB5F-1864-419C-899E-418CABDAE95F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"800da3da189c3717ae4b944549a97eed4a205a7a","datavalue":{"value":{"entity-type":"item","numeric-id":3830528,"id":"Q3830528"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e8094974e244e9a9362ab1027a42b62338fada98","datavalue":{"value":{"amount":"+0.8240004181861877","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":"Q1097029$31475F99-4792-4F5D-9612-F442A8E39BED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"27892da789ec64a61bb4a94ede8ee9e963026fe8","datavalue":{"value":{"entity-type":"item","numeric-id":908700,"id":"Q908700"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"007154a46dfd240f553a690066ea5f8760bbdb30","datavalue":{"value":{"amount":"+0.8108990788459778","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":"Q1097029$A07FEF05-D94A-4954-8682-9826DC2DE2C2","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A note on complete problems for complexity classes","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/A_note_on_complete_problems_for_complexity_classes"}}}}}