{"entities":{"Q1083192":{"pageid":1093944,"ns":120,"title":"Item:Q1083192","lastrevid":42864463,"modified":"2025-07-15T12:42:41Z","type":"item","id":"Q1083192","labels":{"en":{"language":"en","value":"Complete divisibility problems for slowly utilized oracles"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3976330"}},"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":"Q1083192$0E1C40B3-9E4B-4A82-B428-A20B1344A447","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"9bb74716186e826637baf0f26396c9a6db56fe0a","datavalue":{"value":{"text":"Complete divisibility problems for slowly utilized oracles","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1083192$31D8363B-CE8C-426E-ADCB-B88292C903DD","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"c9870ea97b3f1eb26476a7f43c877df73574cd87","datavalue":{"value":"0604.68044","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1083192$E8E86512-76DC-490D-B606-99F573C369DA","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"9fdabb61126bde631345c9c32d03cfd1208e712b","datavalue":{"value":"10.1016/0304-3975(85)90017-9","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1083192$FF305CF6-89FE-4546-88DC-66D485172FE4","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":"Q1083192$44E3238E-9F71-426F-A695-09A2AD1FE75B","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"3c94df5c9af0ede578c52141befd29044de13172","datavalue":{"value":{"time":"+1985-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":"Q1083192$CB2C9D14-767A-4064-801F-42919203550A","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"b6bc701c0f10dcc85ad2e61bd2f666691b05ebcb","datavalue":{"value":"The concept of NP-completeness relative to a slowly utilized oracle is introduced and shown to be useful for providing evidence of intractability of some problems that are not known to be NP-complete. One such problem is to decide if a sparse polynomial has a root in the integers (mod p) for prime p. Relationships between unrelativized complexity and complexity relative to a slowly utilized oracle are also given.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1083192$7949F889-D9BD-4CB1-81D5-E571FCFAAC1C","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1083192$772012B8-30FC-4DA8-AE3A-62DB3DD16248","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5005488ac12471348bfecb95099a57fd4da722ac","datavalue":{"value":"11T06","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1083192$D49E9F9C-6E72-42C0-B407-82ACF5080788","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6be78f1bad1f2f19058dbde65eb124c0430a7d27","datavalue":{"value":"68W30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1083192$1D02E2DC-EE94-408F-B751-E6DF96C3884C","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"8692898a9fd6402098f3f49c2554889f597f7feb","datavalue":{"value":"3976330","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1083192$EA1194F4-ABFC-41C1-8168-37A0F571CC1F","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c0a051f7ea468a9b169398712fb7a5731c108b29","datavalue":{"value":"polynomial divisibility","type":"string"},"datatype":"string"},"type":"statement","id":"Q1083192$4C41C028-361B-46BE-85C3-F4BB72F60B4E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f7cb2762c4702f37abf0593ceebb0a29e79ddbe6","datavalue":{"value":"NP-completeness relative to a slowly utilized oracle","type":"string"},"datatype":"string"},"type":"statement","id":"Q1083192$1C851605-7A36-47CB-AD51-422FE7932548","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"41e712b3e4e3e6e09e1cf21493dde485ad82b860","datavalue":{"value":"intractability","type":"string"},"datatype":"string"},"type":"statement","id":"Q1083192$10685602-40D3-42AB-BAB3-648423087E87","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"85d3765f45ce58420ee8c8f7e642d785c15d3b3f","datavalue":{"value":"sparse polynomial","type":"string"},"datatype":"string"},"type":"statement","id":"Q1083192$F5488180-B909-4B33-86C3-CB33B578115F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3ad9fe8451e89b8926289829c79b98e5de8484c1","datavalue":{"value":"root","type":"string"},"datatype":"string"},"type":"statement","id":"Q1083192$3F634B71-426D-4761-A022-CE22127554F9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2494270b18d41624a37bea210a22309e31ce286b","datavalue":{"value":"unrelativized complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1083192$02748B70-21A0-4E69-A029-D4D36B714652","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"64ff6cd5e30126fbb3f3f53ba155b3fb492a941d","datavalue":{"value":"complexity relative to a slowly utilized oracle","type":"string"},"datatype":"string"},"type":"statement","id":"Q1083192$386FFFBF-49D3-44F3-A169-E4D93A4FFFD7","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"34f99c9947f4d98af9da609b6496b55645bbe075","datavalue":{"value":{"entity-type":"item","numeric-id":1238600,"id":"Q1238600"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1083192$68C3B81D-9B99-4B3A-B694-39AD38172613","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":"Q1083192$B71B25DD-ACA6-455A-B2FC-608EEEEB1B19","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"be488889250be07ade3cf56526857d17880c45cd","datavalue":{"value":"https://doi.org/10.1016/0304-3975(85)90017-9","type":"string"},"datatype":"url"},"type":"statement","id":"Q1083192$27A18E80-4165-4737-A8A7-AD9A16F0747B","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"26b8a39922ecc435407309089f0a62c6289ecb5e","datavalue":{"value":"W1973529901","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1083192$040BEC66-9106-4543-BDFE-72F15F606EDF","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"6c4b58f9e8478a4210509de111b81e4ccd911506","datavalue":{"value":{"entity-type":"item","numeric-id":4086709,"id":"Q4086709"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1083192$24E78C80-710D-43C4-8305-D6704D48BCCC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"54e3771f8171656e0aed45bf0777afe8aad7a3a9","datavalue":{"value":{"entity-type":"item","numeric-id":3902480,"id":"Q3902480"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1083192$68308DD5-3773-466A-8E68-18DC86604C9C","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":"Q1083192$F2627075-F012-4CB7-AAED-2547925F6EE5","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":"Q1083192$896AF8BF-FF08-4475-995D-BE56388031C3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c9a89887e764d4ad510aeae08c2dd3e7f471e6ec","datavalue":{"value":{"entity-type":"item","numeric-id":1132906,"id":"Q1132906"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1083192$C9877835-42DC-4A15-AD0A-A4B6433CEDAE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1bbaa88fa4bc73a806971af91313862449fcfadd","datavalue":{"value":{"entity-type":"item","numeric-id":1062447,"id":"Q1062447"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1083192$AAB9EE6B-FBEF-4B68-9AD9-F6C1EF954064","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e04afb7aaad50511123ad782b63d6693415fcdb5","datavalue":{"value":{"entity-type":"item","numeric-id":4167579,"id":"Q4167579"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1083192$01D68014-A05F-4FCE-8409-118AFACC2421","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"38d0995cbd889a4e114eebf7fd4a98d2bce26aeb","datavalue":{"value":{"entity-type":"item","numeric-id":1238601,"id":"Q1238601"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1083192$0389E070-8393-47C7-BD4C-06198FFE7F24","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ff777be63b91ba136763fd1864340ab7856c51e4","datavalue":{"value":{"entity-type":"item","numeric-id":3910619,"id":"Q3910619"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1083192$F17BD857-55E5-468A-A8A8-EA475FA0DCE1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d7af518f21abbf673f84ab6d1aa24c3c52eef081","datavalue":{"value":{"entity-type":"item","numeric-id":1230622,"id":"Q1230622"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1083192$180C1F3C-6E04-449C-A77A-F7ADD60C47BA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"90b2e9ef80870f750a8e7c2c7417511c25bd9ed4","datavalue":{"value":{"entity-type":"item","numeric-id":3048250,"id":"Q3048250"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1083192$CE144BD7-5029-4941-B513-714B04195176","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b366749ad0286ebd932eb8e06d0605e833fa070c","datavalue":{"value":{"entity-type":"item","numeric-id":1918949,"id":"Q1918949"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"044c61b87eee732016cfd4859b2b52f859a6802d","datavalue":{"value":{"amount":"+0.86492044","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1083192$E76237EA-DDAF-4EC1-B5D7-DB7FD217AC36","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"44f45d564b62d74412680dd328bdd0f8ffbcb5fc","datavalue":{"value":{"entity-type":"item","numeric-id":4635845,"id":"Q4635845"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"645f3fca288032eee4003125d7cac37f8b4cc0e4","datavalue":{"value":{"amount":"+0.8574164","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1083192$46B122E2-B4F8-499E-8C30-CB8A2FB55EE6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"16aab8ca0489996d79239cb963b5070cc816851f","datavalue":{"value":{"entity-type":"item","numeric-id":6115442,"id":"Q6115442"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"637d618974221df536a5c29d6cd54990eaa3460c","datavalue":{"value":{"amount":"+0.84979653","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1083192$EA9FF165-30A4-40B3-B9E1-CD978B93DC12","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"90d6895661eaf0df7c642b39a7f2ada9bd12b2e1","datavalue":{"value":{"entity-type":"item","numeric-id":1920128,"id":"Q1920128"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9f6e54fd80f9c66a511551d289eb8d3a65aeb4f5","datavalue":{"value":{"amount":"+0.84309596","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1083192$DCC62CF1-FAA5-4D3E-AEB2-2466AB86C407","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"60f4e064537a348eccf57c8ea304f1b616a4753c","datavalue":{"value":{"entity-type":"item","numeric-id":1346911,"id":"Q1346911"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e2e5297982cd7e177cc406eca52cf7d4b103859f","datavalue":{"value":{"amount":"+0.84268725","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1083192$3B21E28F-CE7D-4223-A5B8-99D803CBC267","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9df12cf3f350293a19ea2ddd8ccce26d7d9da5d3","datavalue":{"value":{"entity-type":"item","numeric-id":5131778,"id":"Q5131778"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a502c84fb00a2d05e7be5d24ba21ac582c15551c","datavalue":{"value":{"amount":"+0.8401928","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1083192$47AB5999-A877-49DD-91F9-2E10A6DCC7F0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e70e0fe95db3b5c41648f00c6a14fdae715dcc53","datavalue":{"value":{"entity-type":"item","numeric-id":2693692,"id":"Q2693692"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4fbc4ed707c113f7c0a6472267008a178964567a","datavalue":{"value":{"amount":"+0.8373685","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1083192$61A36B1C-611B-4D92-A9F0-9AE78078EC06","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"91773b0c6bb5d8ea1f4ea867b2964473bef74a64","datavalue":{"value":{"entity-type":"item","numeric-id":5061877,"id":"Q5061877"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e76f748bc7b388e42176aeeb7e4306474ce51fc9","datavalue":{"value":{"amount":"+0.8372848","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1083192$EA22FEA3-A77A-4C85-A2EC-1977CE17A845","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9650c01859cc53fd32ceb972b66649cda4571afc","datavalue":{"value":{"entity-type":"item","numeric-id":1119570,"id":"Q1119570"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"54c7b130dc8d4fd0055eda2facd6f4faec99dd9a","datavalue":{"value":{"amount":"+0.8370887","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1083192$BAAD4E43-DB20-40C3-B5DB-67D0FE7B5197","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a5bf62e7887061fc215f2c5110e8f620aa26d253","datavalue":{"value":{"entity-type":"item","numeric-id":3809784,"id":"Q3809784"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"54c7b130dc8d4fd0055eda2facd6f4faec99dd9a","datavalue":{"value":{"amount":"+0.8370887","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1083192$F4678D87-7D5E-4281-BBDD-2C2206E1FC6E","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1083192","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1083192"}}}}}