{"entities":{"Q918200":{"pageid":920048,"ns":120,"title":"Item:Q918200","lastrevid":65370963,"modified":"2026-04-12T02:07:24Z","type":"item","id":"Q918200","labels":{"en":{"language":"en","value":"An explicit separation of relativised random polynomial time and relativised deterministic polynomial time"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4157880"}},"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":"Q918200$F729070C-1069-4091-94F5-05439BF8E924","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"ad1e0c1a6d22702373e13fe4bad5e919d02ec628","datavalue":{"value":{"text":"An explicit separation of relativised random polynomial time and relativised deterministic polynomial time","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q918200$A4B2D14E-E0F1-4F73-8C20-2D94784B6823","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"7652590242ae75c687e198b68cc170f31ed0b6ef","datavalue":{"value":"0705.68054","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q918200$9ADE6860-CBA9-40BC-807E-538BD1AD3F6F","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"4bdefa505eb56e78716cd723f0a53de050ef3b3b","datavalue":{"value":"10.1016/0020-0190(89)90143-9","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q918200$BDBCB100-A21A-4224-A3C9-ED4AF23C30EB","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"4ba6b3ff672379f2eff5613ba6334cfe39ede532","datavalue":{"value":{"entity-type":"item","numeric-id":286967,"id":"Q286967"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q918200$9CCEA843-514E-4E22-BCEB-97A98B15DF82","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":"Q918200$1288DF75-72BB-4BC7-8998-12E0FAF13017","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":"Q918200$D1434CC7-23E4-4C13-AB46-F98AFD3BBA28","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"895b365d9cdd3a5f49591c43c337702568f676f6","datavalue":{"value":"An important problem in structural complexity theory is determining the relationship between the class of problems solvable in deterministic polynomial time and those solvable in random polynomial time.    The author considers the problem of interpolating a sparse polynomial P from its values. An essential component of determining P is the somewhat simpler problem of showing that P is not the zero polynomial. It is shown that, given certain information about P, no deterministic polynomial time algorithm can distinguish P from the zero polynomial. It is shown, however, that there exist probabilistic algorithms that distinguish P from zero in random polynomial time. For the more general problem this implies that P cannot be determined in deterministic polynomial time and that yet there exist probabilistic polynomial algorithms.","type":"string"},"datatype":"string"},"type":"statement","id":"Q918200$E51EACAB-15B8-4E68-8352-58513C826920","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b4346faa01bb5fb0576370374d6456afd58d5666","datavalue":{"value":"68Q15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q918200$71E873DE-EFB1-4C8D-AF7C-A32A428E755B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d7656d1c841701431b0b3d99d23720089a267cbb","datavalue":{"value":"03D15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q918200$2E035347-DC49-4582-9DDB-42BEF0D76EDB","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"c5627c8639bdca847ad7aca7defe602f3e551017","datavalue":{"value":"4157880","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q918200$9F59C8B1-0939-4570-9FF6-703E8D69FF4F","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"726ebfcf2ef9d97cdf0e74a68d8365ab8fb09bdb","datavalue":{"value":"random polynomial algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q918200$13E2C4D4-27EA-4016-94A9-BF1BA3FB5336","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"25a0d0a64145a26d41eb5308b1cb512dc20d7b36","datavalue":{"value":"computer algebra","type":"string"},"datatype":"string"},"type":"statement","id":"Q918200$2A431A16-123D-48E5-8DDF-F6F4537C8E48","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f31b1c16132074888aa1436091f252968a03f48e","datavalue":{"value":"zero testing","type":"string"},"datatype":"string"},"type":"statement","id":"Q918200$4D29F02E-ED32-45E9-9486-CECBFBB88EBD","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":"Q918200$9868F1F4-3512-4FFA-8B96-9F542843BEA8","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"6ab025f1ca2c84198d1bfbfe1580971df128717a","datavalue":{"value":"https://doi.org/10.1016/0020-0190(89)90143-9","type":"string"},"datatype":"url"},"type":"statement","id":"Q918200$1E356DE7-ACDB-40EE-8D3D-8CF6E1412D4A","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"655d7012ac75bb989e25206611c73e71f8f303c2","datavalue":{"value":"W2050393190","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q918200$9D9DE609-D281-4BC6-9F07-A183C9C9B542","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"8b1a601d2d325d59af7d202f1f94462edd810b86","datavalue":{"value":{"entity-type":"item","numeric-id":3495652,"id":"Q3495652"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q918200$F52CF4BF-D80C-4DC2-8FA4-18488D1BAF8E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d6a1bce69a33139ec859758c4b116b3c648bdce2","datavalue":{"value":{"entity-type":"item","numeric-id":3942397,"id":"Q3942397"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q918200$460738B6-EF1D-45EE-88A4-108AECB4E96E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f06e660485cbc895c0095c4f085a34cde29ca5c0","datavalue":{"value":{"entity-type":"item","numeric-id":3765250,"id":"Q3765250"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q918200$6FDAECF3-4030-4245-8137-BF3A4413A2FD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"45693627939fec63d2836fa11bb5f307d8dbed5a","datavalue":{"value":{"entity-type":"item","numeric-id":3899517,"id":"Q3899517"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q918200$87DCDAAC-0C13-45D9-B221-CBC138F04759","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d73e5fdcd2644fcf8851cd00097d32d1e30f5f00","datavalue":{"value":{"entity-type":"item","numeric-id":3851616,"id":"Q3851616"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q918200$77804266-0E08-4775-A72C-F46027D07634","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1a25a1fa95e7799812e4dba2e2a4326ed74549c9","datavalue":{"value":{"entity-type":"item","numeric-id":915342,"id":"Q915342"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q918200$22CED2FC-89BA-4349-8BEC-8FAE17D1A79A","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6a17c392a71105067cb778e4165f40fe6bcbad7f","datavalue":{"value":{"entity-type":"item","numeric-id":3750121,"id":"Q3750121"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"011ac9dcef497ab6a22c0769861a420bcaad2ce3","datavalue":{"value":{"amount":"+0.7714466452598572","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":"Q918200$C3898BD6-002E-48CC-91C4-5DAA8405D61D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9501be0087701c203b2ca0bf71db7819703b7202","datavalue":{"value":{"entity-type":"item","numeric-id":5286848,"id":"Q5286848"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"77cc7278908c8435d1c9552d90390ba7f6192a57","datavalue":{"value":{"amount":"+0.7656942009925842","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":"Q918200$2224AA32-342B-4621-A133-361F768C1C41","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a238728d80777ed63b53ee73dfc12795b085a7cf","datavalue":{"value":{"entity-type":"item","numeric-id":5175971,"id":"Q5175971"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"18ad18d0e2aff76e723354b4d567e902589065cc","datavalue":{"value":{"amount":"+0.7513352036476135","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":"Q918200$F68959E3-DF39-40EE-86E5-7F155FB53CCB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8a9c8cc9cf0fdf66963c1473c3272f0d0c68e5e9","datavalue":{"value":{"entity-type":"item","numeric-id":5204322,"id":"Q5204322"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7dc7f05ed7f1a6345c0fd98dea29007dabe90d7e","datavalue":{"value":{"amount":"+0.747149646282196","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":"Q918200$5A362568-1A1A-4B30-B636-624CC2BB72F1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b22422e3c22972c4ba0963db5868465079487633","datavalue":{"value":{"entity-type":"item","numeric-id":5928878,"id":"Q5928878"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f19b22ca96ea8f5c53d5cb2bf7a6b7f15cf3fa1f","datavalue":{"value":{"amount":"+0.7469546794891357","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":"Q918200$84F97883-5BB2-47A2-B761-CE2E6B085701","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"An explicit separation of relativised random polynomial time and relativised deterministic polynomial time","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/An_explicit_separation_of_relativised_random_polynomial_time_and_relativised_deterministic_polynomial_time"}}}}}