{"entities":{"Q582102":{"pageid":583869,"ns":120,"title":"Item:Q582102","lastrevid":62948739,"modified":"2026-04-11T09:11:15Z","type":"item","id":"Q582102","labels":{"en":{"language":"en","value":"On the polynomial IO-complexity"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4130021"}},"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":"Q582102$C988C070-8336-4147-BCBE-171FC44BD667","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"ad1907de48eb17f6929842a92104b812e7827746","datavalue":{"value":{"text":"On the polynomial IO-complexity","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q582102$A35F95AB-D1B8-4588-A8B6-C3F0B1F2FFE1","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"7fd096b2ce056c423c26aced2f3a535425a34a96","datavalue":{"value":"0689.68069","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q582102$1631EAE6-F5F8-4FBC-A496-93D3D9CE6065","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"c4b35ae752f901ee86308fc96f2f8a4b06904970","datavalue":{"value":"10.1016/0020-0190(89)90141-5","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q582102$0B62E483-6469-485F-B522-4C20CBF4E4C2","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"0285ddcf48bfa01b49ae6da8524072296d5b93b0","datavalue":{"value":{"entity-type":"item","numeric-id":582101,"id":"Q582101"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q582102$ECF968A9-94CF-4C72-A2F1-F5B99E189382","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":"Q582102$A567E5F2-7777-42AB-836A-52671397AA99","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":"Q582102$53B8A7DA-8D6B-4705-899D-82B3FCA09212","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"4398b841f4aa8bcb93690037e886720f39e1533e","datavalue":{"value":"We want to know the relationship between the class P and NP and the new defined classes P(d(n)) and NP(d(n)). We show that there exists a positive density function d(n) for which P(d(n))\\(\\neq NP(d(n))\\) if and only if \\(P\\neq NP\\). On the other hand, we also show that the existence of a positive density function d(n) for which \\(P(d(n))=NP(d(n))\\) implies that \\(E=NE\\), where E is the deterministic exponential class and NE is the non-deterministic exponential class of languages. Using the concept of density function, we give an alternative proof that NE\\(\\neq E\\) implies NP\\(\\neq P\\). The implication NE\\(\\neq E\\) implies NP\\(\\neq P\\) was already known. This was showed using the concept of tally sets by Book, and using the concept of sparse sets by Hartmanis.","type":"string"},"datatype":"string"},"type":"statement","id":"Q582102$733B6B28-C46F-4E4C-859B-BFAB63478726","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q582102$12E50F73-2320-4009-9018-C1C827AD27DC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d7656d1c841701431b0b3d99d23720089a267cbb","datavalue":{"value":"03D15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q582102$66CB31DB-4654-4A8C-A5AD-7730275A2348","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"34a57b655c575f1675cb59f337952d03cd57c8c7","datavalue":{"value":"4130021","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q582102$FDCE0D20-3F4A-467D-8A67-DE03F68E78A7","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"168f70398022e63696a8eb2c5ec278f1c6130c22","datavalue":{"value":"IO-complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q582102$24742E30-8895-4687-B6CF-95461A515E72","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e6fb3908bc773a3c8dcab1b40a40883840b18de8","datavalue":{"value":"sparseness","type":"string"},"datatype":"string"},"type":"statement","id":"Q582102$6432110C-2BC6-4284-A390-A9858B451BE0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c90dabac5ca2a3b4f523fa6eed5fdfe603bc0e7c","datavalue":{"value":"P","type":"string"},"datatype":"string"},"type":"statement","id":"Q582102$01751716-6A5D-43E8-9C23-C7B0F198E34F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"834c45d526445b63ede129bf0252d3b47bed13e5","datavalue":{"value":"NP","type":"string"},"datatype":"string"},"type":"statement","id":"Q582102$23574FB5-D8EB-4CAE-A5F6-045D55569407","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a01ee01077a14e69c3c27408efccd7f448855eec","datavalue":{"value":"density","type":"string"},"datatype":"string"},"type":"statement","id":"Q582102$C4A8D712-AAEF-473F-9066-08884C035845","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cafca52f6717dfa0d2eda8e3b69ea87245ea8f29","datavalue":{"value":"E","type":"string"},"datatype":"string"},"type":"statement","id":"Q582102$623DBC9F-7CDC-4637-9631-9D47C6401F2E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fbbbad80b3ebdd4a171f20feb0686e8dcfd1efd0","datavalue":{"value":"NE","type":"string"},"datatype":"string"},"type":"statement","id":"Q582102$993F9A99-5798-45C2-B505-BA7393AE6E1A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b9746a8dd2f5e7ede4a11aab28c1f86fb6b61348","datavalue":{"value":"tally sets","type":"string"},"datatype":"string"},"type":"statement","id":"Q582102$1C01E021-0914-466C-9116-5FB1802C9F4C","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":"Q582102$1D43C64C-E05D-46AE-9A8E-0563C65361C7","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"cc4e870fcd21971f8b54dbc131b4dae2091db645","datavalue":{"value":"https://doi.org/10.1016/0020-0190(89)90141-5","type":"string"},"datatype":"url"},"type":"statement","id":"Q582102$2F1607B4-9C2C-4D0C-A151-AD8AE83499B2","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"61d29c46be0c603817049053c9c89d71b63d615f","datavalue":{"value":"W2009806555","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q582102$1060FE9F-864E-412B-9C54-1D491F349D34","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":"Q582102$1955703C-E5B2-4C38-A266-CD632B610DC6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"832499cf0ccfa2d1ac23baccd2406bd0aba8e2a7","datavalue":{"value":{"entity-type":"item","numeric-id":5625127,"id":"Q5625127"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q582102$7C57BBC8-1773-46D3-99B6-FF16DA6EBB6F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bb09716bd57a1011f7c259b1047b4d21b39a969d","datavalue":{"value":{"entity-type":"item","numeric-id":4775472,"id":"Q4775472"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q582102$14C9CBEF-C36F-4E0A-BF68-D6881B49D8CB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"27ae048a51566b9b30aabd668fe3c01dba8252d3","datavalue":{"value":{"entity-type":"item","numeric-id":1172386,"id":"Q1172386"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q582102$252E03C5-A13F-4B54-A894-ABC403A87810","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"91437bc3f5649edc6a7acb3095e2cdec844eb2e9","datavalue":{"value":{"entity-type":"item","numeric-id":3711749,"id":"Q3711749"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q582102$602D3585-5008-4AF8-8C47-547AB26094C0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3da510a58b16c0736f10bd517df8e982dda6dd9c","datavalue":{"value":{"entity-type":"item","numeric-id":3922170,"id":"Q3922170"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q582102$CBB5DAF6-C716-4797-8D9B-334BA767F1B8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"07d8ba8c05b76f81fededbac5225f1410ec870bf","datavalue":{"value":{"entity-type":"item","numeric-id":1112018,"id":"Q1112018"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q582102$185A5F3E-64BE-4D3D-9221-C1111D2445A2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"62600b58c4a6534286c776968945d508a1261ea3","datavalue":{"value":{"entity-type":"item","numeric-id":1120281,"id":"Q1120281"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q582102$2E32CF9E-C62C-4C6B-9EED-F9C5D7AAEE83","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d02d11b9d55ebaf37bd8de936abd707d57beddf1","datavalue":{"value":{"entity-type":"item","numeric-id":2894481,"id":"Q2894481"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f2642d613399527d395786b34c661d829a5aab98","datavalue":{"value":{"amount":"+0.7558324933052063","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":"Q582102$1D25310F-FB78-4390-9645-771D70D950CB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4526197cea57d61ea9a889706123ca2b147c7ed2","datavalue":{"value":{"entity-type":"item","numeric-id":1348523,"id":"Q1348523"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9f2abb3f1246e7923aecb8315d09b800243f6f39","datavalue":{"value":{"amount":"+0.7443972229957581","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":"Q582102$7E628CD6-3742-4564-B182-A2DF8608FD1D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"47a754c2c78144db9ce70fb3b161393b7f9d0941","datavalue":{"value":{"entity-type":"item","numeric-id":4238424,"id":"Q4238424"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ca45c52720809dbac1dbc04be9b7784ac18be05d","datavalue":{"value":{"amount":"+0.7341364026069641","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":"Q582102$7C49D7C3-3655-4608-A2FA-FCB6686BF1BC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d71d7948e0f1c5c6fdb4011e20ab67860753a3c2","datavalue":{"value":{"entity-type":"item","numeric-id":3751007,"id":"Q3751007"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ef1440b721c0b995dfc7630a286f258311abdd7b","datavalue":{"value":{"amount":"+0.7335755228996277","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":"Q582102$5619B480-10B4-43F1-8F8E-C4FBD301CE8E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c16d16f5658aa39d9dbe6d3d6e450ef918143ffc","datavalue":{"value":{"entity-type":"item","numeric-id":4281492,"id":"Q4281492"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"274fc9429eed7ed7d7216af027bc042c57ae7d7f","datavalue":{"value":{"amount":"+0.7253308892250061","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":"Q582102$B81C3E26-2358-45DB-AD25-78757F171693","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On the polynomial IO-complexity","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On_the_polynomial_IO-complexity"}}}}}