{"entities":{"Q676314":{"pageid":678163,"ns":120,"title":"Item:Q676314","lastrevid":63645744,"modified":"2026-04-11T14:34:58Z","type":"item","id":"Q676314","labels":{"en":{"language":"en","value":"Strong polynomial-time reducibility"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 992113"}},"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":"Q676314$690C71E6-2D2A-4247-87B5-7408E56469DA","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"77369f4ded2fa3caf6c2158133558ba75b0882ce","datavalue":{"value":{"text":"Strong polynomial-time reducibility","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q676314$9C5E11BB-27A7-4EE1-8F4D-5E14157EAAE1","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"8f46b442b2c4bd46cef16629d0dbed55233a73d8","datavalue":{"value":"0865.03035","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q676314$F1BF03CB-BF6F-4B68-9947-AC2E7F936F7C","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"1f383aa6a004a28b9b383c29567da93d36ebe0b3","datavalue":{"value":"10.1016/S0168-0072(96)00037-1","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q676314$ADB3603A-6E19-4A23-8172-44823D9504EB","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"c2db9bcc35a63fe39fea97a564bc4a4c838a41e8","datavalue":{"value":{"entity-type":"item","numeric-id":676313,"id":"Q676313"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q676314$28E6CFF3-82E3-4EEF-83B7-1E14C009827C","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f91a4bcbc93435aed71775d25a4c5cd09e26f12d","datavalue":{"value":{"entity-type":"item","numeric-id":122505,"id":"Q122505"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q676314$95AA4049-649F-43D6-B65D-C27A0D60CE7B","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"c3556926a7495ff0c5ad9c786087e5ca19eed455","datavalue":{"value":{"time":"+1997-06-11T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q676314$044DEECC-3358-4DA8-B3A1-4F11189D2E5D","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"22e59615a973195b995f54bf382b977b4c81e0b5","datavalue":{"value":"If \\(f\\) and \\(g\\) are functions then \\(f\\leq_T^p g\\) if there is a polynomial time algorithm, with access to oracle \\(g\\), that can compute \\(f\\). Take the set of all polynomial bounded functions (that is, they don't grow too fast). If \\(f\\leq_T^p g\\) and \\(g\\leq_T^p f\\) then we will say \\(f\\) and \\(g\\) are equivalent. This paper considers the structure of these equivalence classes (called degrees) under \\(\\leq_T^p\\). In this paper the author shows that, for this structure, (1) if you look at all the degrees less than a given set, they do not form an upper semilattice, (2) a weak form of the exact pair theorem holds, (3) every degree is the sup of a minimal pair. The last result is in contrast to degrees of functions where a non-diamond theorem holds.","type":"string"},"datatype":"string"},"type":"statement","id":"Q676314$18ED24E9-32E8-46E3-8335-E6BA7497022A","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"379be2ae88ac653823960287ba517e23fc9265f4","datavalue":{"value":"03D30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q676314$04348B2B-67D7-4E5F-8112-11179DF1A14B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b4346faa01bb5fb0576370374d6456afd58d5666","datavalue":{"value":"68Q15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q676314$36A70EBC-56A6-49BD-A4A2-C824680B948B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d7656d1c841701431b0b3d99d23720089a267cbb","datavalue":{"value":"03D15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q676314$C4734CC6-75D6-4BED-9B27-691E9CDE68B6","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"69f48b0a2cf9e31b25ceead9d3f83d3215eb65c8","datavalue":{"value":"992113","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q676314$1078FEE3-F103-4A4D-BFF6-B3719265D52C","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0ca57d225358d55c161d2fd9284b1f4649a91fc4","datavalue":{"value":"polynomial-time reducibility","type":"string"},"datatype":"string"},"type":"statement","id":"Q676314$07049B5E-309C-47DD-99EF-F5689AEC285C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ac873341ab34d6db98676ef037e18583cae25841","datavalue":{"value":"oracle","type":"string"},"datatype":"string"},"type":"statement","id":"Q676314$6B28C820-1B5B-4A0B-A246-3249460EAB73","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"35b8a1394abd2e1a70a68e47338693b93146f451","datavalue":{"value":"exact pair theorem","type":"string"},"datatype":"string"},"type":"statement","id":"Q676314$2D7D9AAA-B98A-44F0-A6F7-781B9B41F537","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"089045109444783772792da658bd57f5bf33eabb","datavalue":{"value":"minimal pair","type":"string"},"datatype":"string"},"type":"statement","id":"Q676314$A1B9378A-F867-454E-B563-F17B701565E0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"11d33b439fe3f901c3c44fe99f23b0e5820fd196","datavalue":{"value":"polynomial Turing degrees","type":"string"},"datatype":"string"},"type":"statement","id":"Q676314$D569D576-70C9-4BBC-9B31-DD5ADA228719","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ce7ab89ef0afcd2141c7da8aae338608bd16ac9a","datavalue":{"value":"automorphism","type":"string"},"datatype":"string"},"type":"statement","id":"Q676314$64822C99-3E05-4C84-91C1-622E70DA3406","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"59c02125cd654c6fe0740c84a942b089a0294819","datavalue":{"value":{"entity-type":"item","numeric-id":811135,"id":"Q811135"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q676314$9A7BDE00-13DA-428C-9C6D-DBB226354740","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":"Q676314$FDB615B9-CBEA-4C9C-9FC0-656CDB9D174E","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"2a0199e65c145119638fa58789304520ac28cbf5","datavalue":{"value":{"entity-type":"item","numeric-id":909455,"id":"Q909455"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q676314$89EFF8C3-6E5B-4DFA-89F2-73A01FB7DD81","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"266b63e1b4f2f925a39aebd27fa77fcc3bc563c9","datavalue":{"value":{"entity-type":"item","numeric-id":5096783,"id":"Q5096783"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q676314$3D3BBDAE-2DC6-4301-98F8-3043CAB9FDDB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"933e265aaacf91ad02327976a9648dfce105352c","datavalue":{"value":{"entity-type":"item","numeric-id":1314385,"id":"Q1314385"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q676314$C184BF17-254A-49A1-9DC7-6A78616DD5AD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a0024b4464965f980056a704c96252adf0643859","datavalue":{"value":{"entity-type":"item","numeric-id":2277252,"id":"Q2277252"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q676314$90540A9E-B1B9-4330-B3CC-FF47C2BAA659","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a086cb300a7a30e8a6932087c63d77f171e64716","datavalue":{"value":{"entity-type":"item","numeric-id":1201882,"id":"Q1201882"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q676314$3596896D-0430-42A9-A311-14C99E4A45A4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e3c77053f249ea7e82cd40265fa301ebde3267a8","datavalue":{"value":{"entity-type":"item","numeric-id":3781091,"id":"Q3781091"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q676314$24E3F82F-0A72-4C7C-BEAF-C76793202B86","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":"Q676314$98B4BE54-6A6B-41AD-BB77-8B3ED17D5666","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fe67cddb1d2e8d4582eb3ba360c56bb29576a54c","datavalue":{"value":{"entity-type":"item","numeric-id":3329452,"id":"Q3329452"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q676314$805CF0C1-BA43-4716-9E53-E7FED9E1240A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3589abe08309ee0c80b87d4a4fa6a10bf824c734","datavalue":{"value":{"entity-type":"item","numeric-id":1235011,"id":"Q1235011"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q676314$1F8CB95C-2DF9-4386-A23E-890FC4D06207","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3cb26dcca5a66b90f50581f28b1ff636a9297aea","datavalue":{"value":{"entity-type":"item","numeric-id":1139064,"id":"Q1139064"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q676314$AC40B8BA-20D4-43F8-9A3F-965750C288B7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"38f99c9040626540b18257b25ff5b59d89de1832","datavalue":{"value":{"entity-type":"item","numeric-id":4009812,"id":"Q4009812"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q676314$2336B05E-7FEA-46E6-9279-B2DBD243B95F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5a4b2cc56da0887f83cf9332aa80e63bf68370c4","datavalue":{"value":{"entity-type":"item","numeric-id":1193873,"id":"Q1193873"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q676314$62E41379-FD94-421A-980D-E590CD431E25","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ee6c66b2ac7f5947fe7308ba1ca97c70ca857a52","datavalue":{"value":{"entity-type":"item","numeric-id":1405796,"id":"Q1405796"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e323b7379abf7dfca4e8bba3f26662ad704a5ec1","datavalue":{"value":{"amount":"+0.93891114","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q676314$8247D1A8-FB9D-4C2E-ACD9-F39E6ABC2E39","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f8e85e69c97abfeb1a1b7ede13608a12658b9b4a","datavalue":{"value":{"entity-type":"item","numeric-id":4733404,"id":"Q4733404"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ffba8e72b815943d49f7bdaa5327b5e4bd328a06","datavalue":{"value":{"amount":"+0.93626803","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q676314$8873B2EB-8921-4510-840B-3E6A3053F3F8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c016ee6b1645c4306a96e67ca6eb5c3d55877323","datavalue":{"value":{"entity-type":"item","numeric-id":2799750,"id":"Q2799750"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3e1c2b01ad4352c7562796bded49e67be4be3bab","datavalue":{"value":{"amount":"+0.928831","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q676314$4A50FA15-FF81-4230-8122-E527043FD46F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7f2ffe01037fb3311529b4ea35b1b5ad8c5d29ab","datavalue":{"value":{"entity-type":"item","numeric-id":4934293,"id":"Q4934293"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"eb7a1bcb36d5a7a28e71a75ea5774ec352023c0d","datavalue":{"value":{"amount":"+0.9206804","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q676314$FA566618-68BF-4DF7-ADB9-E566D197FEF1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1e00d4b43c72ecf7a0dfd62d8dd2a74cdd978aca","datavalue":{"value":{"entity-type":"item","numeric-id":3107360,"id":"Q3107360"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ac25004ad135ea4306c623d217224841989e6705","datavalue":{"value":{"amount":"+0.9158586","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q676314$E338C54A-BC79-4928-8FA1-03C64ED7256C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ca4d02e555b9d891ef7c4280539903606eb05341","datavalue":{"value":{"entity-type":"item","numeric-id":5096158,"id":"Q5096158"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a01991b5c093480f8e1cbcb6e977b85873f8436f","datavalue":{"value":{"amount":"+0.9152992","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q676314$573B472B-388E-461C-A5E3-CCF905A5F2A0","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":"a01991b5c093480f8e1cbcb6e977b85873f8436f","datavalue":{"value":{"amount":"+0.9152992","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q676314$A121746B-2AEC-4D64-B794-E6907B64D1B1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ac7af6e6f2115f82b78b2f21e90f50953efaeea9","datavalue":{"value":{"entity-type":"item","numeric-id":2364655,"id":"Q2364655"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d04862071704c89f9816d609292ad7bfa01987e8","datavalue":{"value":{"amount":"+0.91045606","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q676314$764A47D0-E061-4C2A-9FBD-D3723B77F758","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bfee4e001601e340d50b91ff0d09a5de7469fb13","datavalue":{"value":{"entity-type":"item","numeric-id":1201882,"id":"Q1201882"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a5b8793fb55039c343e75f2ed11f876c790c6f04","datavalue":{"value":{"amount":"+0.9024743","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q676314$C04C86F0-AFCB-476B-A63C-4AC1C3CD9F62","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5c9936da627a9a1bd188069410bfcd14aa0b4a3f","datavalue":{"value":{"entity-type":"item","numeric-id":1177170,"id":"Q1177170"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"abbeaf63069dc60c92053f2b22b45d83d0beb879","datavalue":{"value":{"amount":"+0.8988765","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q676314$4847DAA5-AF37-4DB8-95F5-7F304717ACC5","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Strong polynomial-time reducibility","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Strong_polynomial-time_reducibility"}}}}}