{"entities":{"Q1999993":{"pageid":2010735,"ns":120,"title":"Item:Q1999993","lastrevid":78339143,"modified":"2026-05-06T11:21:28Z","type":"item","id":"Q1999993","labels":{"en":{"language":"en","value":"Nondeterminisic sublinear time has measure 0 in P"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7074487"}},"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":"Q1999993$4F8A5FA7-1038-4953-A5CB-2288276DA33E","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"cb9718b5607bbb6f348b11c576be7465c6ee5135","datavalue":{"value":{"text":"Nondeterminisic sublinear time has measure 0 in P","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1999993$14E1A4C7-E63C-4F1B-994B-57A84FEFB4DC","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"5169f322f3207177278a9ccbd5f7f581d64b298c","datavalue":{"value":"1459.68076","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1999993$F5866043-ED5B-422B-8A2E-7E6479BFD74E","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"3ee1f3cf09e866f3eab6561711e5db4300ad48b0","datavalue":{"value":{"entity-type":"item","numeric-id":596116,"id":"Q596116"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1999993$A5EA1C4D-63C9-473C-89CD-AD13D8E5E453","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"51aa1b3fcbcb16c20a482e3aa5f70fc56309989d","datavalue":{"value":{"entity-type":"item","numeric-id":1999992,"id":"Q1999992"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1999993$39D89A48-7289-4F4E-8583-405A0BDCA3FA","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"b559743f011d61696dff04b2ecd3408df2541e49","datavalue":{"value":{"entity-type":"item","numeric-id":169698,"id":"Q169698"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1999993$73BA528B-FA81-445F-A600-124EDC4BD4DE","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"34188037f8b0cd35688ae234ade090010846bddd","datavalue":{"value":{"time":"+2019-06-27T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1999993$A44140BF-CBC6-434B-B1F7-A2B4E0C0DBB5","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"0a055d343ab0413070c94e88b9951e666788caa7","datavalue":{"value":"https://arxiv.org/abs/1801.05884","type":"string"},"datatype":"url"},"type":"statement","id":"Q1999993$A3A5708E-950E-4C3E-A64B-17A3810FA95E","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"80bc7e64104c8cb4c701281059aaf6e758d214a8","datavalue":{"value":"In [\\textit{J. Cai} et al., ``Constant-depth circuits and the Lutz hypothesis'', in: Proceedings of the 38th symposium on foundations of computer science, FOCS 1997. Los Alamitos, CA: IEEE Computer Society. 595--604 (1997)] it is proved that \\(\\mathrm{NTIME}[n^{1/11}]\\) has measure 0 in P. This implies the analogue of the measure hypothesis in P fails, because \\(\\mathrm{NTIME}[\\log n]\\) has measure 0 in P. (The measure hypothesis is a quantitative strengthening of the \\(\\mathrm{P}\\not=\\mathrm{NP}\\) conjecture which asserts that NP is a non-negligible subset of EXP.)  \\par In the paper under review the authors improve this result by showing that the class of all languages that can be decided in nondeterministic time at most \\(n(1-\\frac{2\\lg\\lg n}{\\lg n})\\) has measure 0 in P. In particular, the nondeterministic sublinear time class \\(\\mathrm{NTIME}[o(n)]\\) has measure 0 in P.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1999993$134D2475-6F6F-4AA3-940A-3D932C133651","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b4346faa01bb5fb0576370374d6456afd58d5666","datavalue":{"value":"68Q15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1999993$4C4A8B44-2DC7-4406-AE77-033C3EE41912","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1999993$46F7515A-B544-4186-943E-930D515A8955","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"1ed402cfb6ce9079ecfddb682c16eedb132e62e3","datavalue":{"value":"7074487","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1999993$90743DA9-AB6B-4685-9B9D-144035A4B3E5","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"dd49eaa402407c98be68608ef7dc24a70d0dc5ac","datavalue":{"value":"nondeterministic time","type":"string"},"datatype":"string"},"type":"statement","id":"Q1999993$35E033D7-1330-4755-B821-0127151C4D12","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e0674f302b9d85b437d4d8e9710f7da3d268f9d3","datavalue":{"value":"DNF width","type":"string"},"datatype":"string"},"type":"statement","id":"Q1999993$61F8D81C-02AB-4ADC-8BE9-9FB7B27FF1F7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"85df2159416ea410f93c99226e1a1d26b39d99fd","datavalue":{"value":"resource-bounded measure","type":"string"},"datatype":"string"},"type":"statement","id":"Q1999993$99464DBC-4E36-4CB0-B9EC-0895D497B13B","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"7c0f9a5de2afd25d103c132e1617d4201a3c58e4","datavalue":{"value":{"entity-type":"item","numeric-id":591972,"id":"Q591972"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1999993$D1A2C909-440B-438D-A423-B12467C56685","rank":"normal"}],"P1463":[{"mainsnak":{"snaktype":"value","property":"P1463","hash":"ce514966e327ded3c17917f258854330d9f0ecdc","datavalue":{"value":{"entity-type":"item","numeric-id":18319,"id":"Q18319"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1999993$4C6550D5-4B06-4390-B19E-7F3CA9264971","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":"Q1999993$4F8FD8EF-C25C-443D-8BB2-99A189E36435","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"06168967a4555d2306f199b4695f1112f1a74c4f","datavalue":{"value":"W2963265603","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1999993$12CE08DB-07E3-4184-9A16-68090112E22F","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"e8e8c30651594c1eb9c8a2e2ed6c4a6e32cf1c7f","datavalue":{"value":{"entity-type":"item","numeric-id":4732106,"id":"Q4732106"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1999993$E7123333-0AF5-4BB2-9C07-E2EA5E0050C3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4617d4a70f53c6043d4f9efd489af5070386087c","datavalue":{"value":{"entity-type":"item","numeric-id":3569004,"id":"Q3569004"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1999993$D414ED89-1C16-4764-89BB-3A659600387F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6506cf877dd8d1aab96664441c77bb321682231f","datavalue":{"value":{"entity-type":"item","numeric-id":4348122,"id":"Q4348122"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1999993$5F3A59CB-A7D9-4163-905B-032FD893B7EF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d38b4a76df166b15ffd8426406cd56803e157294","datavalue":{"value":{"entity-type":"item","numeric-id":1190985,"id":"Q1190985"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1999993$4104CBEF-4B2F-4010-B581-356F3BA7BDD5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ecb9b7e017fc45acb5cb1d99b55a4850b0de87dd","datavalue":{"value":{"entity-type":"item","numeric-id":4359463,"id":"Q4359463"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1999993$546DEB51-9319-4BFE-B87A-965909C0068A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"795bab1ee13e73ea624f513fe56ebff1ce1cd950","datavalue":{"value":{"entity-type":"item","numeric-id":4429684,"id":"Q4429684"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1999993$6AA3D21B-0ED4-4704-81E2-7C6F40BF8D73","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"898f7abebb2110166fa4d903fdadc4d54bc027a6","datavalue":{"value":{"entity-type":"item","numeric-id":671427,"id":"Q671427"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1999993$D37E960B-12CD-4D41-8F89-A64867B4716C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7c9985f6f87a12e675c0a4ce5a1c70bbd22a418a","datavalue":{"value":{"entity-type":"item","numeric-id":4266481,"id":"Q4266481"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1999993$DB4CF320-84B0-4607-A9C3-4464DAB80C16","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f2c01e4b683a8844e24ad27f013b3f8988740259","datavalue":{"value":{"entity-type":"item","numeric-id":930913,"id":"Q930913"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1999993$5AAED4D6-E533-4D73-9F85-6FC5503BEA5B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"574a6599f545ec08b9afa71a7573eae29e700904","datavalue":{"value":{"entity-type":"item","numeric-id":5166888,"id":"Q5166888"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1999993$0AB532B0-AE30-4F7F-BF93-395B9851382D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7d5bf339bd162c9e6a2fc1206b7db3ba41cc38fe","datavalue":{"value":{"entity-type":"item","numeric-id":1362904,"id":"Q1362904"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1999993$6899D7AB-177B-4AD9-AAB0-6941A780C881","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"f95c0e0e0aaeac3b1b0a65688b61ba3addf7f7ce","datavalue":{"value":"Q129599535","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1999993$4C7B1997-EFF1-4C73-8397-A90935A6E147","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"0fc3e962a9769c805f8c09f54553eef1bb2ce9ab","datavalue":{"value":"10.1007/S00224-018-9875-0","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1999993$CB94D695-0357-4441-AAC4-378CB0DC511B","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9d0c85e38fc5207562d8e03a770528015c400d21","datavalue":{"value":{"entity-type":"item","numeric-id":4258583,"id":"Q4258583"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4fabdeda7354094b0d2812d2c14d010c83994ba2","datavalue":{"value":{"amount":"+0.7546905875205994","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":"Q1999993$360CE7A1-B8BA-4CB4-B058-4261C6F3A8FE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ec1544c83ef541829508dc70631e9e16c2eb6bb9","datavalue":{"value":{"entity-type":"item","numeric-id":5465865,"id":"Q5465865"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5833fa934936ae19fd67a9e14d7527baf9620e20","datavalue":{"value":{"amount":"+0.7444673180580139","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":"Q1999993$95709FD0-0009-405E-B178-2A531B23BDC4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7a1a77bad880b4d4088b60010894c2f2300470e9","datavalue":{"value":{"entity-type":"item","numeric-id":1816731,"id":"Q1816731"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3977c3f78e33809438292ef201923f91d5f86915","datavalue":{"value":{"amount":"+0.7436584234237671","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":"Q1999993$CA26CC70-517B-4F98-88CB-652FA2FF1510","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4e5ba26e12a463c2f030c88b16861f9195c5de23","datavalue":{"value":{"entity-type":"item","numeric-id":937197,"id":"Q937197"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f8a897b64e97bef7efe08733522c7c3330033fea","datavalue":{"value":{"amount":"+0.7436118721961975","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":"Q1999993$51B64B76-58CC-4C56-B552-1B5E77842BB7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"06835a9ba0564d13f25d8c93d54f1991cd82f14c","datavalue":{"value":{"entity-type":"item","numeric-id":4305356,"id":"Q4305356"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e83db52b0ca439ccda0c4e50377a6a7603d9bb8e","datavalue":{"value":{"amount":"+0.7433530688285828","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":"Q1999993$0E812C20-9B4C-4123-869D-68E2F9395775","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Nondeterminisic sublinear time has measure 0 in P","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Nondeterminisic_sublinear_time_has_measure_0_in_P"}}}}}