{"entities":{"Q791316":{"pageid":793164,"ns":120,"title":"Item:Q791316","lastrevid":64368459,"modified":"2026-04-11T19:23:44Z","type":"item","id":"Q791316","labels":{"en":{"language":"en","value":"Bandwidth constraints on problems complete for polynomial time"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3850473"}},"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":"Q791316$25B0F1AE-4953-4F09-A397-83514433B8B0","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"32ba41e152e071e7caf7c5a42eefdd1fca0a9f49","datavalue":{"value":{"text":"Bandwidth constraints on problems complete for polynomial time","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q791316$2268806F-2652-420C-81E2-7874B3025662","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"b4ab0ba75067a7d6d4d0bad11ab77f3b8d56771e","datavalue":{"value":"0535.68021","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q791316$2B4311D7-7EE7-488F-9FF3-87CABBB26F8E","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"2b4f0102339b5993e3a7c289774e6fc9bab54bc0","datavalue":{"value":"10.1016/0304-3975(83)90078-6","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q791316$BF70C20B-142C-4F1A-91D5-C4DED0EBFF28","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"619555d96850b0d2a63f38f6976c99450dd5b2d1","datavalue":{"value":{"entity-type":"item","numeric-id":791315,"id":"Q791315"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q791316$9C27EEAF-B964-4471-A6E0-3227848AF5B1","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":"Q791316$FDCFFCC7-0F97-4EBA-892E-6C0B87C5B0F1","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"0136733d5dd7d9f4d36f24c87a0b8375ae1cb2fd","datavalue":{"value":{"time":"+1983-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":"Q791316$100F4D6F-6D3D-47FB-8D9A-A6D071D1D309","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"10fb6ef72e051ce8c32acedc7b0350be214bd972","datavalue":{"value":"The admissibility of a path system problem is considered. It is shown that its monotone version with a bandwidth f is log-space complete for the class of languages recognizable within polynomial-time and space f. Basing on this result it is ascertained that the class of sets accepted within polynomial-time and simultaneously polylog space coincides with the class of sets reducible by log-space transformations to sets accepted by one-way log log-space bounded alternating Turing machines. An inclusion for the alternating class \\(ASPACE(f)\\subset \\cup_{k>0}DSPACE(2^{kf})\\) is proved where the function \\(f(n)=g(\\log \\log n)\\) satisfies the following condition: for every integer m there exists \\(c>0\\) such that for almost all n an inequality \\(g(n+m)\\leq cg(n)\\) is valid.","type":"string"},"datatype":"string"},"type":"statement","id":"Q791316$9A67001C-EAA5-472F-9246-08DE47933315","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q791316$98531144-D202-4786-A98F-70773112378D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q791316$EFE2CF8E-10D2-4199-91DB-D2DD9860F2FC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q791316$55FCC925-89B1-4EF2-BA92-E0723A3462D4","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"fa384918aff2dfbb3e9ec69023a3c470151104b7","datavalue":{"value":"3850473","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q791316$B471C972-39BF-474D-ACED-02F91E26ECD4","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"283c82c44a17991d4a68c30a04cdf799ac3917b9","datavalue":{"value":"path system problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q791316$B8A9C44C-1C3F-4707-93FE-6BF1E35380F8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5d68a802d85bbba1ff8d1a571b3ef4f42eb91b93","datavalue":{"value":"bandwidth constraints","type":"string"},"datatype":"string"},"type":"statement","id":"Q791316$E3EDC1D9-500C-492A-A5BC-D9A7BA6AF367","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0d8d8d18b9bf0ddea3bcb878925738b2dd7dce67","datavalue":{"value":"time-space alternating classes","type":"string"},"datatype":"string"},"type":"statement","id":"Q791316$E423C159-9077-47D4-AFDE-735E825C2B0D","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":"Q791316$B12A0C55-9D4C-4A49-96CC-E10313C82A06","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"3af0a230945993644ceff53706481cbd34f8e345","datavalue":{"value":"https://doi.org/10.1016/0304-3975(83)90078-6","type":"string"},"datatype":"url"},"type":"statement","id":"Q791316$B374B63F-6EE4-460D-9C1A-51D6AE5E7A1E","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"e1215907293e1b07bd0037ed1b2090d5d60e8eb4","datavalue":{"value":"W2053805167","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q791316$5B851D3F-EE22-4B59-AA26-46440E128C39","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"a6c9f60d59d03f74d07d7e9b8bc3ab838c64afc2","datavalue":{"value":{"entity-type":"item","numeric-id":1251077,"id":"Q1251077"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q791316$75F352E6-AFDA-472A-AE13-C2589A163ED1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"796811902c381e96346a417ef4f337ccc7487b4d","datavalue":{"value":{"entity-type":"item","numeric-id":5524803,"id":"Q5524803"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q791316$C2E6BF91-3DF8-4E11-BA18-97728A038C24","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"63190e09b804c247a0206f6525d276592b41ae69","datavalue":{"value":{"entity-type":"item","numeric-id":5674871,"id":"Q5674871"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q791316$0A325B67-CE02-4E8E-87D6-776B7A40EEB7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e86a79bfcfca810fb7601492bd0551fae9de8408","datavalue":{"value":{"entity-type":"item","numeric-id":4142697,"id":"Q4142697"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q791316$A1562572-5CB2-4B26-B067-B45153029CAA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"648af4444efef3dfface63422920536bd2b0c180","datavalue":{"value":{"entity-type":"item","numeric-id":3928246,"id":"Q3928246"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q791316$E1A98DA6-3489-4EB1-B9EE-6DD8F0EABF59","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fef9484315c67d77706e16383c6414fc536d21d3","datavalue":{"value":{"entity-type":"item","numeric-id":2561468,"id":"Q2561468"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q791316$F2CFF63E-1771-4174-B1CE-E9680EA40177","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"468123f607fe9c0a7affbe6709664ebec53c9057","datavalue":{"value":{"entity-type":"item","numeric-id":3956994,"id":"Q3956994"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q791316$D1350D80-A701-4969-86C5-5536FA2BF290","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0445ca81f1046c8b5bea1a2062f174b139078383","datavalue":{"value":{"entity-type":"item","numeric-id":1217591,"id":"Q1217591"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q791316$252089B7-7711-41AE-AF2E-A03D63342613","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d9285a61f3039e7ce640456a9ea2b4d13665dc77","datavalue":{"value":{"entity-type":"item","numeric-id":5626625,"id":"Q5626625"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q791316$AF341CB0-16D8-4BE1-8FB7-8A06A9B45313","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"12c6f50eb5a5939405c1877dfdfbe7a7d53f3f7f","datavalue":{"value":{"entity-type":"item","numeric-id":3944008,"id":"Q3944008"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q791316$6469B08F-9D14-40E8-A750-7FCF362540B7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9757ce980c6f8fa87d540ce34490987cfec8474c","datavalue":{"value":{"entity-type":"item","numeric-id":1218269,"id":"Q1218269"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q791316$47189E4D-0F2F-455A-A9E0-4B9A14130A61","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"93abefd43f60c4734d29bc653212ccc79b537d1c","datavalue":{"value":{"entity-type":"item","numeric-id":4165413,"id":"Q4165413"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q791316$33A2A7C1-B2F9-4871-B2D5-5A7732771CAA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"66856e28a8d065ae00cc1eb109ee4001e24e8421","datavalue":{"value":{"entity-type":"item","numeric-id":5582355,"id":"Q5582355"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q791316$4E2A4636-365F-498B-B08C-33CD6307B276","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2043397a54eaa38033021fac24881dafefacec7d","datavalue":{"value":{"entity-type":"item","numeric-id":5592246,"id":"Q5592246"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q791316$3C93ACAB-80E2-4234-9B3E-2B346EB531C8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4bcd71ac0ee1662e3c5c0f5046af9d7c75419ed0","datavalue":{"value":{"entity-type":"item","numeric-id":1221749,"id":"Q1221749"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q791316$34421ADC-B9D7-4B86-83AA-37A7B01C2DBA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4f0d34bbb1dc9b4f992285ff669f2af1e56f7e0e","datavalue":{"value":{"entity-type":"item","numeric-id":4192112,"id":"Q4192112"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q791316$291C0769-4626-42C6-AB6E-1CF7AA99037A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"24f4aba8e0ee3a2966b3de817d74f8875ab291ae","datavalue":{"value":{"entity-type":"item","numeric-id":1223124,"id":"Q1223124"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q791316$E5D2F1F4-EC0D-453F-BE53-FB39F152CCAD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a6de891d5a6744d6bc5da3b977613039967f9d10","datavalue":{"value":{"entity-type":"item","numeric-id":4191603,"id":"Q4191603"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q791316$2995E648-EF99-4794-9D27-D2F47D203219","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0751213ac1721d4b7bcbd9ddb031d0ca4971a705","datavalue":{"value":{"entity-type":"item","numeric-id":1145502,"id":"Q1145502"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q791316$B441F892-2914-4D14-B718-66677667D83F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9920c3ac00d626f59f95283223bd4fb6ae680345","datavalue":{"value":{"entity-type":"item","numeric-id":1152951,"id":"Q1152951"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q791316$55C1B596-AC07-4C8D-9FAB-056DE61F203D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"736a1d463d18d2f300e2b9600c3f86eae2986ef8","datavalue":{"value":{"entity-type":"item","numeric-id":2537313,"id":"Q2537313"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q791316$C70DB21C-2507-4418-AF79-3FDB5BEC3DB3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a4f200ddc20c2d33390fb94670a066f08d95c0e9","datavalue":{"value":{"entity-type":"item","numeric-id":1215271,"id":"Q1215271"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q791316$843517F8-4B36-493F-9DF9-7225AD2FF525","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"59a71ee27fc06ad3b0b4b92d7dad58a5649789e7","datavalue":{"value":{"entity-type":"item","numeric-id":4158497,"id":"Q4158497"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q791316$3781E642-8FE1-4C7A-9CA7-514DFF478AAD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a0e11de7132c10164732e9b26841e64c659613e5","datavalue":{"value":{"entity-type":"item","numeric-id":4142695,"id":"Q4142695"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q791316$0EF5051E-DEBF-4302-81DC-B7E471664181","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"173002dfec884ea3ca9ffd82acac676a83274a5a","datavalue":{"value":{"entity-type":"item","numeric-id":1151259,"id":"Q1151259"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q791316$99388D25-A667-48A6-A362-04F779B02F20","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"c70aad50ad6f9599713b21f203c4d59f70c50468","datavalue":{"value":"Q127662435","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q791316$7C7751DB-ADDE-41A6-B792-D321850F91E7","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5d55cc9bbf51b480bd72eafb5c091773bf183c60","datavalue":{"value":{"entity-type":"item","numeric-id":1064779,"id":"Q1064779"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cbf3f39d2c63559850c290d61a959537d9982590","datavalue":{"value":{"amount":"+0.7940518856048584","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":"Q791316$9D39485D-A1D6-41B4-9526-E309E71875F9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fa82dc0720d1d3ce37ab93ca5e1cbba583cb4cc0","datavalue":{"value":{"entity-type":"item","numeric-id":1822500,"id":"Q1822500"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4df65d2923ada51e8763fbad6347d95f05a4cd29","datavalue":{"value":{"amount":"+0.7832099199295044","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":"Q791316$C8B7A66D-37AF-4691-AA76-BCA926A9A0D1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e04546efc41dad6d5fc4dddd71909771876c6131","datavalue":{"value":{"entity-type":"item","numeric-id":1262855,"id":"Q1262855"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"37b427b061a9ed70458214ec6ec5982379318d36","datavalue":{"value":{"amount":"+0.719194769859314","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":"Q791316$70B56129-C99C-4A4E-A20E-25DB8B628E57","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"92216762b5aa1ab5ca4eb2388959f1b7f2b75d6a","datavalue":{"value":{"entity-type":"item","numeric-id":1261484,"id":"Q1261484"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"410ca70000a4fcce19b2204f9eb577d193189fd9","datavalue":{"value":{"amount":"+0.7000191807746887","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":"Q791316$A885A2C4-6EA3-4FA0-ACBB-45B0BC2B85FC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1a8e6c0f0eef20dcde3eb270dc97c3a60555a420","datavalue":{"value":{"entity-type":"item","numeric-id":673904,"id":"Q673904"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ce49a484a5fd3d858f07127d2b1667a86f95c449","datavalue":{"value":{"amount":"+0.6998458504676819","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":"Q791316$60724465-BE31-42C9-99CA-1768DCA4AEE2","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Bandwidth constraints on problems complete for polynomial time","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Bandwidth_constraints_on_problems_complete_for_polynomial_time"}}}}}