{"entities":{"Q3711749":{"pageid":5741655,"ns":120,"title":"Item:Q3711749","lastrevid":50542802,"modified":"2026-01-14T08:34:24Z","type":"item","id":"Q3711749","labels":{"en":{"language":"en","value":"Sparse sets in NP-P: EXPTIME versus NEXPTIME"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3940727"}},"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":"Q3711749$B28C9E04-7A76-4B48-B79A-3729D94C66B2","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"987395bcb8b2fc45065ece1963876ec80df7d63b","datavalue":{"value":{"text":"Sparse sets in NP-P: EXPTIME versus NEXPTIME","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q3711749$CA74249E-66D1-4A3D-948F-9E131FAB650C","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"1ff4f3e0ba72c11d9c817a54b93412c2ce798b80","datavalue":{"value":"0586.68042","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3711749$62533AAB-BB25-48ED-88A0-D1F7A9E0C952","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"c7419094ea3658ecd1d0a20a3aa1a3458369a998","datavalue":{"value":"10.1016/S0019-9958(85)80004-8","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3711749$FF3EEE60-6693-4339-BD8A-139B4E87A057","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"73ca8ead30de6ed9f10b7d2317387852b8cc90d9","datavalue":{"value":{"entity-type":"item","numeric-id":3711748,"id":"Q3711748"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3711749$A6B999A8-379B-4B9D-B25F-174E907F0E92","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"f24581060e1fc674d2a5c7705dc19743c7374ca5","datavalue":{"value":{"entity-type":"item","numeric-id":1071499,"id":"Q1071499"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3711749$4B3EB523-4F02-4F63-A423-D2EDC49C42F5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"c9449ce466a2c684a15ed4352b5933311b5f46f1","datavalue":{"value":{"entity-type":"item","numeric-id":6482617,"id":"Q6482617"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3711749$AD3E1E1E-F8B8-44B2-974A-A63DE0C827E8","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"4434820098e3b6c980c31814818af7c68f56bd22","datavalue":{"value":{"entity-type":"item","numeric-id":2832035,"id":"Q2832035"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3711749$1F0AD88C-8D56-4EEE-A849-3E77F270FEDF","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":"Q3711749$C2FC3388-1881-4D2C-819C-4953B1E1599C","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3711749$8B3D9F96-A4DC-44D9-AA54-AF4EB9283956","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d7656d1c841701431b0b3d99d23720089a267cbb","datavalue":{"value":"03D15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3711749$43A37554-8CF0-4C4D-8FE3-3B88597DF08B","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"ae8a67f5ee826a91d39d7e60b8996ed1c5bea173","datavalue":{"value":"3940727","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3711749$7AF7A873-D0F6-43C6-AB41-47E5B10E4507","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f1d12e51f7d2438567b51bfce46972f6255ef9f3","datavalue":{"value":"exponential time","type":"string"},"datatype":"string"},"type":"statement","id":"Q3711749$485428E0-7DE9-4319-A165-D8B2FB3289CD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"35b5110463d3ec5de0b71107ca30a96a1cf1be33","datavalue":{"value":"structural properties of the sets in NP-P","type":"string"},"datatype":"string"},"type":"statement","id":"Q3711749$CB38F61B-20E3-47DA-B261-39BF54D18032","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a01ee01077a14e69c3c27408efccd7f448855eec","datavalue":{"value":"density","type":"string"},"datatype":"string"},"type":"statement","id":"Q3711749$002968C0-8C83-4431-9033-300FD7989516","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5e05c223122524c997bbdd0009f587dae504b8e3","datavalue":{"value":"lower density sets in NP","type":"string"},"datatype":"string"},"type":"statement","id":"Q3711749$173C6003-0525-479E-A216-47BA8598745D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f2492b46695d2490c83f348518fadd0defd33a22","datavalue":{"value":"time-bounded complexity classes","type":"string"},"datatype":"string"},"type":"statement","id":"Q3711749$2FD52AB5-DF27-4855-AED3-EDADA941B16C","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":"Q3711749$9595AE71-2D5F-4F22-B6A0-BAB354822EC5","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"d1145a638bffa36c3fa11d4372163884dc702661","datavalue":{"value":"https://doi.org/10.1016/s0019-9958(85)80004-8","type":"string"},"datatype":"url"},"type":"statement","id":"Q3711749$90DB6AA9-B54B-408C-9EAC-8F9BA6BE67C4","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"707a15ed8b30b74dbc070225db07469a3259268b","datavalue":{"value":"W2090841650","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3711749$EF9FCDBE-4170-40F6-BFC7-1182A88CCED2","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"858bf8e1752cc6af1a35c3d09145f8745b00664f","datavalue":{"value":{"entity-type":"item","numeric-id":4596657,"id":"Q4596657"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4daa67d0d02bc40c76da42e5b1b776a2026dd095","datavalue":{"value":{"amount":"+0.8269888758659363","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":"Q3711749$85F999B9-5B4F-4373-80EC-0E5696EDE6A6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5a0b73a2bc53462960d269e364d851ab40513251","datavalue":{"value":{"entity-type":"item","numeric-id":4336273,"id":"Q4336273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"232740a361dd76747332e0009e0b0804ff3484a1","datavalue":{"value":{"amount":"+0.8029012680053711","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":"Q3711749$E47D4C27-6311-4396-B4DB-C5D01EA7B4AF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1b02eb2f508eb09802b6b266326c109d1c0033a3","datavalue":{"value":{"entity-type":"item","numeric-id":3315500,"id":"Q3315500"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6e197b8804d0f77b54235327f8722aab414e25af","datavalue":{"value":{"amount":"+0.797908365726471","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":"Q3711749$9C665526-9B63-4770-A27B-1E7390E6E605","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"66d114d81f2be89079ef0147a3eded71c2c174f9","datavalue":{"value":{"entity-type":"item","numeric-id":1854459,"id":"Q1854459"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"73cfd22a1e4df6e770657f4d5b91d167453344ca","datavalue":{"value":{"amount":"+0.7896758913993835","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":"Q3711749$D7E63CDB-A97D-4CF3-96F1-7D247EACBF14","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e15b996c276ccc4ba58ba0871d17ffb6b8ab2eb7","datavalue":{"value":{"entity-type":"item","numeric-id":3346297,"id":"Q3346297"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"73cfd22a1e4df6e770657f4d5b91d167453344ca","datavalue":{"value":{"amount":"+0.7896758913993835","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":"Q3711749$772FF569-6301-4930-B12A-B020D9BCC16E","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:3711749","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:3711749"}}}}}