{"entities":{"Q1095660":{"pageid":1106412,"ns":120,"title":"Item:Q1095660","lastrevid":69826914,"modified":"2026-04-13T10:36:47Z","type":"item","id":"Q1095660","labels":{"en":{"language":"en","value":"Two time-space tradeoffs for element distinctness"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4028900"}},"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":"Q1095660$91000C5B-E8A9-469A-BD01-35A84E32A40C","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"52fc6b17b7baec7e8a8729a5b8b6f23d5dfd7c76","datavalue":{"value":{"text":"Two time-space tradeoffs for element distinctness","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1095660$69A4F748-D2F2-42B0-AA45-676A0CC35D00","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"bd59e81806d5d05c99f04e38b25fd13793e75e8b","datavalue":{"value":"0632.68044","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1095660$E8536832-2F2B-4C11-B59F-0B27755BBB09","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"9a4578d602ef3ec39638d913aed3538206f84cdf","datavalue":{"value":"10.1016/0304-3975(86)90150-7","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1095660$E935D7E1-EA45-4DCC-B59E-E382DF598E7D","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"61162cb60b7871c6c335756c3fdcecbc875a3787","datavalue":{"value":{"entity-type":"item","numeric-id":1095659,"id":"Q1095659"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1095660$442EDF54-28FB-4149-9B36-FA1F27B888BF","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":"Q1095660$3679D371-2A50-4B7B-8923-96731C761A12","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":"Q1095660$E19A2249-2D0E-4AD4-869E-09AB0BF7BEF5","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"d7aa8279db2b4f5180998dd083de0befccfa4714","datavalue":{"value":"Two time-space tradeoffs for element distinctness are given. The first one shows \\(T^ 2S=\\Omega (n^ 3)\\) on a branching program using minimum operations. By a result of \\textit{A. C. C. Yao} [ibid. 19, 203-218 (1982; Zbl 0547.68062)], this implies the same bounds for linear queries. The second result extends one by \\textit{P. D\u00fari\u015b} and \\textit{Z. Galil} [Math. Syst. Theory 17, 3-12 (1984; Zbl 0533.68047)] who constructed a Boolean function that requires \\(T^ 2S=\\Omega (n^ 3)\\) on a k-headed Turing machine. Here it is shown that their proof also holds for element distinctness, a more natural problem.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1095660$3EA69713-0637-487F-8E1C-BDE7CAB34317","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1095660$54B36239-56D2-4304-B30C-F14770D6204F","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"67687a804e8e12e05ac2288f17128012c32b7796","datavalue":{"value":"4028900","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1095660$FD4939FE-401A-48BB-8620-52C8BEDBB7D5","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d1669e93b8ab0689fd7b4733c7e588e51c536a05","datavalue":{"value":"element distinctness","type":"string"},"datatype":"string"},"type":"statement","id":"Q1095660$02C5EBEA-F2B5-412C-8BC6-5D047933E6CB","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":"Q1095660$182D3A89-C099-4D10-9137-DE8853C97ECE","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"e41365c32c7ea36889fd9cb922f7df64c68191d0","datavalue":{"value":"https://doi.org/10.1016/0304-3975(86)90150-7","type":"string"},"datatype":"url"},"type":"statement","id":"Q1095660$C091ADF2-DA7E-4757-A145-0A422CD0AFAC","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"431c7b009a23ad8a5c6f168cab0097273124c513","datavalue":{"value":"W2003223355","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1095660$E3C4F381-0DAB-4AF8-83E4-31A199A2711B","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"cfda1aaef4d74a55b724a4e4b97259bc5a577f06","datavalue":{"value":{"entity-type":"item","numeric-id":3936210,"id":"Q3936210"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1095660$5236F4D3-B619-4440-9969-BFF31725EABE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"35e9ec39f3ba7097c2d3bbc2ec715934f4e4f7c1","datavalue":{"value":{"entity-type":"item","numeric-id":3745272,"id":"Q3745272"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1095660$E57A3C5E-14C2-4837-B8AB-E446D889505F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d1a52569f4723473b14a228edfd70f44f49aae34","datavalue":{"value":{"entity-type":"item","numeric-id":1152950,"id":"Q1152950"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1095660$97C2C1B1-12D1-45EB-8E08-F24AD1735E59","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"44c3aa1f109b7982536744b5c71615445bc3e192","datavalue":{"value":{"entity-type":"item","numeric-id":3316594,"id":"Q3316594"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1095660$DE5C5D4E-BFE7-40A2-A6BA-254600F1CCB7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"aebb0025125315526bf4ca176bd7c0c9089c4c2c","datavalue":{"value":{"entity-type":"item","numeric-id":3960129,"id":"Q3960129"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1095660$B4353854-4CDC-4BF9-A772-1EA7D539F9BE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"88400135b49f4397bf174ec3e94f5ee990b34d20","datavalue":{"value":{"entity-type":"item","numeric-id":1140426,"id":"Q1140426"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1095660$8EAED03B-9723-4CDB-9B51-6B6E06ABCE61","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bd1b00a7994a3ca9800739057812732d2acfae5a","datavalue":{"value":{"entity-type":"item","numeric-id":799115,"id":"Q799115"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1095660$841B39AA-C35F-4B2D-832C-DF8D9C703B5E","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"39d544507dbf65a79abbab9d5a65f3661b632ea3","datavalue":{"value":{"entity-type":"item","numeric-id":3776617,"id":"Q3776617"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3d915050949af086a4325c752185975cecffa9fe","datavalue":{"value":{"amount":"+0.9824712","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":"Q1095660$31E7D5C3-9ACC-4E63-942E-05F1F57ADB56","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"50b66aca1c181525e86467a0660971c54bc78356","datavalue":{"value":{"entity-type":"item","numeric-id":3745272,"id":"Q3745272"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3d915050949af086a4325c752185975cecffa9fe","datavalue":{"value":{"amount":"+0.9824712","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":"Q1095660$564254D1-32DE-47D9-821D-9761B8B45D55","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f582cfda81a9197cc01adfe6c949161bf74642d9","datavalue":{"value":{"entity-type":"item","numeric-id":4312417,"id":"Q4312417"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c1ad00d2e6793fe3d044a9533fe5dcf12fae6859","datavalue":{"value":{"amount":"+0.966933","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":"Q1095660$CEFA8FA9-3D34-4B12-AE02-C68F81158F4E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bdb3d8df50ecf73cb51a4ac2e80471877e4b39d0","datavalue":{"value":{"entity-type":"item","numeric-id":3210181,"id":"Q3210181"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"db128ae2dbcb8f99c676aded39608e1638458ac7","datavalue":{"value":{"amount":"+0.9014047","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":"Q1095660$489770F4-C177-4199-B57F-AF64F9569A70","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b8875b45de8f9abf4b186f0d8e6d313fa5fcdf30","datavalue":{"value":{"entity-type":"item","numeric-id":4601908,"id":"Q4601908"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bf87c6ba5daf9173a4a9e837f121aab8c375e804","datavalue":{"value":{"amount":"+0.8650869","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":"Q1095660$680FA297-27E0-435E-A5BD-30FA73E0D657","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b848278c8b28dd9e182de790536b10edfef268ed","datavalue":{"value":{"entity-type":"item","numeric-id":1702852,"id":"Q1702852"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bf87c6ba5daf9173a4a9e837f121aab8c375e804","datavalue":{"value":{"amount":"+0.8650869","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":"Q1095660$45408636-4540-453B-9145-EE47C815C324","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0f38e976dc10ae907c0fa358c1a36f939e973eaf","datavalue":{"value":{"entity-type":"item","numeric-id":4636517,"id":"Q4636517"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cef5925be9d84bce142880f7a3d79a3a73ec2d9d","datavalue":{"value":{"amount":"+0.853097","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":"Q1095660$22A5129F-EA0C-4259-98B8-7EEB1EA18A60","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2c531689a543c95de2ecfcc1c35fcefd8db8103a","datavalue":{"value":{"entity-type":"item","numeric-id":2410365,"id":"Q2410365"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f2d0b780644df23fc7b2839aac6a7bebec9283c9","datavalue":{"value":{"amount":"+0.85212314","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":"Q1095660$8DCB25BE-2C4F-494C-B157-FD07F1F80396","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"99fd45930bfecead415c90235132cfc5921c265c","datavalue":{"value":{"entity-type":"item","numeric-id":6083583,"id":"Q6083583"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"22883514ea6c8e094ac7ab99dad31a068724ee44","datavalue":{"value":{"amount":"+0.85207665","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":"Q1095660$74E44655-624A-4259-AD5E-FC30C0514103","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c3789b792ca214ca08ffda7f00c33ab5b3fc5132","datavalue":{"value":{"entity-type":"item","numeric-id":2442815,"id":"Q2442815"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ecd33d0822d5426d8fa14cd1a8ea6439bd15e3d2","datavalue":{"value":{"amount":"+0.84605443","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":"Q1095660$870202DD-4272-48B7-A3B6-2B74D9C3CC89","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Two time-space tradeoffs for element distinctness","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Two_time-space_tradeoffs_for_element_distinctness"}}}}}