{"entities":{"Q1112017":{"pageid":1122766,"ns":120,"title":"Item:Q1112017","lastrevid":67031436,"modified":"2026-04-12T14:26:45Z","type":"item","id":"Q1112017","labels":{"en":{"language":"en","value":"On the relative complexity of hard problems for complexity classes without complete problems"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4077188"}},"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":"Q1112017$5BF8BF88-EE98-4D77-BF79-C190977FCA52","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"45d8fbe59f84b8d60ac2336502456a19ffdc5e4e","datavalue":{"value":{"text":"On the relative complexity of hard problems for complexity classes without complete problems","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1112017$E56240FD-A74D-4C69-9D8A-BD7F9EDA048C","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"bcdd032dc03bc8faeaf44d600fb0214deb64346c","datavalue":{"value":"0659.03022","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1112017$451942D2-5556-48C1-A990-D286B8D49292","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"ded7ae8400416f2241d1b73710328db73c0bc2e7","datavalue":{"value":"10.1016/0304-3975(89)90066-2","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1112017$A22BCB6D-9A56-4C1A-9B4A-9FB3937508D4","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":"Q1112017$67D56F49-C8FF-4103-BB3F-168CEC5180F4","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"7211ad5ca16eb0d22cd0051fff3d0f3af254ceb6","datavalue":{"value":{"time":"+1989-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":"Q1112017$97F8B601-F57A-4135-A815-37BA4F39C24B","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"555c69738e200df8307a8c67d45488fbfbda3d53","datavalue":{"value":"The main result states that any recursive sequence ascending relatively to polynomial time reducibility (p-r-ascending) of recursive sets has no minimal p-r-upper bound. As a corollary it is proved that any complexity class closed under the direct sum possesses either complete problems or no minimal hard problems. Another corollary claims that provided \\(P\\neq NP\\), the partial ordering of NP relative to polynomial Turing reducibility (resp. m-reducibility) is not complete.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1112017$3B3105E9-5EA4-4AC0-8CA6-8018B57DD76D","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"d7656d1c841701431b0b3d99d23720089a267cbb","datavalue":{"value":"03D15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1112017$9A8EE7DA-72F3-4FFF-8A00-B66E7A84330E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1112017$26930593-775C-45B7-894B-D9404254C7BA","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"7232f44236c6facd939bbffe0cbdd33c11efd3a1","datavalue":{"value":"4077188","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1112017$6F4DA3F9-95AB-42D2-9612-0114099DD1AA","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ad43bcd34d069e6f3c71d7afa37e29d215fd1b15","datavalue":{"value":"sparse set","type":"string"},"datatype":"string"},"type":"statement","id":"Q1112017$2C013B4C-CBFB-4F01-BE04-FE7173F2F711","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"16b273759b98cedcfe6d346efa94fac26baf4a98","datavalue":{"value":"polynomial time reducibility","type":"string"},"datatype":"string"},"type":"statement","id":"Q1112017$E7527D69-D5B3-4113-B7CA-E3B356B75405","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a8d9274cbab44b30312fd22862d18c60a30b38ca","datavalue":{"value":"recursive sets","type":"string"},"datatype":"string"},"type":"statement","id":"Q1112017$685195D8-918E-4D2F-A9CC-326ECFE639F8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f8db1726c03c7059c08d69b8aca64a6baa1151a9","datavalue":{"value":"complexity class","type":"string"},"datatype":"string"},"type":"statement","id":"Q1112017$9DBF2698-37C6-4C8D-8BFE-EE57488A1F81","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"158dda8c4a746799a6a46ef33bd6a1c279ad7e69","datavalue":{"value":"complete problems","type":"string"},"datatype":"string"},"type":"statement","id":"Q1112017$A69CB764-7911-4918-A26A-661AE86A94B0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ddfa678240d0c9420f3bb6d7b98370f90ca6be21","datavalue":{"value":"hard problems","type":"string"},"datatype":"string"},"type":"statement","id":"Q1112017$2E05E61F-2516-4E32-ADCB-A5C72E2228A2","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":"Q1112017$3F95F970-CAFD-41DC-857F-462828277620","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":"Q1112017$9FC8CFCC-0A8F-46AF-8E80-AD52662AAB10","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"f26f6055816fcee46ecc4ea39c1f5fac88af6a3f","datavalue":{"value":"https://doi.org/10.1016/0304-3975(89)90066-2","type":"string"},"datatype":"url"},"type":"statement","id":"Q1112017$2FFBAB85-C094-401D-9D61-0DFCB962C40F","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"8a7e2026b0e36c9debccb182f90af76a2e9c0995","datavalue":{"value":"W2065826812","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1112017$7BFAADB1-DED6-48F6-AA2C-6234E376BCA7","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"2e624f8eefcb1931918dabd90e4516ecd170e232","datavalue":{"value":{"entity-type":"item","numeric-id":3220572,"id":"Q3220572"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1112017$3C6590E9-EE58-4C83-AB60-C9D1ADF5ED9F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dceb582de27df796af18e78f104f60dedd0655a7","datavalue":{"value":{"entity-type":"item","numeric-id":1097029,"id":"Q1097029"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1112017$CAA373A9-E925-42AA-BEED-323FBD143014","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c6aa64a3fc986af9a4c33ddb6e751629a18e9067","datavalue":{"value":{"entity-type":"item","numeric-id":3778006,"id":"Q3778006"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1112017$1E811090-3EC8-4CE9-AEF2-D23D4265186A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9af52c66421185c07ca4d865efeb189c0dddc801","datavalue":{"value":{"entity-type":"item","numeric-id":1158964,"id":"Q1158964"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1112017$0C3C45AB-7FB7-48BD-832C-4A3D48F85618","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7eb24dff4005148539085ff5c885035cfccaed69","datavalue":{"value":{"entity-type":"item","numeric-id":4140967,"id":"Q4140967"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1112017$B00D3478-0688-41C3-BA7E-270BB0E021D2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c25925be7f5c292edb63efdcdcacb15993e69254","datavalue":{"value":{"entity-type":"item","numeric-id":1348523,"id":"Q1348523"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1112017$E7618EF3-1B7D-4147-97CB-F1C1EC262155","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":"Q1112017$CE771827-E0C1-4267-9E11-DF1C03D9F97D","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":"Q1112017$216847F1-A56D-4A22-B7FF-533855D1BAB1","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":"Q1112017$4C82B97B-7FAD-4B05-9E39-222480DC0844","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ece2270b16b9fbc48e0a9ac072c1cea045ecd584","datavalue":{"value":{"entity-type":"item","numeric-id":1162811,"id":"Q1162811"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1112017$BCB432E0-FE08-45FD-AA77-131DE89FBBE4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b6139d2fb76790fbc1a2ff20446f11785d8f1488","datavalue":{"value":{"entity-type":"item","numeric-id":1168733,"id":"Q1168733"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1112017$5B36BEA5-E292-4165-B15E-FDE70C2A4B0D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8cefd7574d6776aa0391d0dd90bd375c1811d3f9","datavalue":{"value":{"entity-type":"item","numeric-id":1164414,"id":"Q1164414"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1112017$BA786889-F95A-44CB-9135-9F3847ECF166","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":"Q1112017$F756D54A-6DE9-4279-8909-22B477B5AC68","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":"Q1112017$05110E56-CF51-43DA-8E97-B99F25BE86F2","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":"Q1112017$F20EC922-DAA3-4AB8-BE2E-AC8268D5EA42","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c3fdeac57e6ae30181fb2db5f7f4e10e134e5670","datavalue":{"value":{"entity-type":"item","numeric-id":1232181,"id":"Q1232181"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1112017$B1CED2BB-B326-47EF-951F-088E49D49CF8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3065df023fcb2411980df376c6fc4777f5d291a5","datavalue":{"value":{"entity-type":"item","numeric-id":1241440,"id":"Q1241440"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1112017$1432CFEC-30C1-479E-9CA3-8EB37578C658","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"f5d709e64e220618760954d7ac6a6ca5ad25ed76","datavalue":{"value":"Q128122778","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1112017$76CA6EBF-7CB7-4C23-9F01-17B163DB6A32","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"08e6d9c9f089659f34ed51aeccace6fcd6181f03","datavalue":{"value":{"entity-type":"item","numeric-id":1097029,"id":"Q1097029"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"40efb26520fe1c1e9aa27538f04982fd1b5fc29b","datavalue":{"value":{"amount":"+0.7994175553321838","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":"Q1112017$B97107EA-9E01-444C-AB7B-B395B0CFDCB2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"77374390b02a3ab47003016d40f98a29eb7c39bf","datavalue":{"value":{"entity-type":"item","numeric-id":3824299,"id":"Q3824299"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a8008504a97aa50d00e135472d43e06b62282afa","datavalue":{"value":{"amount":"+0.7866653203964233","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":"Q1112017$7D01AA5B-6438-4994-9239-9A73F977D131","rank":"normal"},{"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":"f70805c441c63c5c7a969c2af0f3eb45bbab7ec4","datavalue":{"value":{"amount":"+0.7810448408126831","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":"Q1112017$717F0FCD-E328-44B2-8CB8-C45E1C2233FD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1d9031b73ffb0f4c256e887d2438ff51cf9e7d9d","datavalue":{"value":{"entity-type":"item","numeric-id":3761699,"id":"Q3761699"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1a03cde9b1763b50526cdc8eb6898fe7647f6a20","datavalue":{"value":{"amount":"+0.7807536721229553","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":"Q1112017$5D273538-E330-4A00-90DF-3290316BB927","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fcfff5619054bd12ca32ae0ace65488f3c303422","datavalue":{"value":{"entity-type":"item","numeric-id":3781091,"id":"Q3781091"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ba614bfcf3af11532566ad7df68e28ad1d9b7f26","datavalue":{"value":{"amount":"+0.7787064909934998","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":"Q1112017$7BBB4E55-896D-4E38-9FBA-47843BCAFDDA","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On the relative complexity of hard problems for complexity classes without complete problems","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On_the_relative_complexity_of_hard_problems_for_complexity_classes_without_complete_problems"}}}}}