{"entities":{"Q2277252":{"pageid":2287995,"ns":120,"title":"Item:Q2277252","lastrevid":49483222,"modified":"2026-01-07T06:09:07Z","type":"item","id":"Q2277252","labels":{"en":{"language":"en","value":"On computational complexity and honest polynomial degrees"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4195924"}},"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":"Q2277252$2484E0B6-8229-4B3E-AAB4-FD4C20B7B3B0","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"14b360d1f813be883a997f6b0840e01d1b0202d8","datavalue":{"value":{"text":"On computational complexity and honest polynomial degrees","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2277252$962B90D2-6271-44BF-B4A0-EB3189D4EDB2","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"83ac6ca96317d4b5c48b6c6d8df99078f39185d4","datavalue":{"value":"0725.03025","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2277252$B88FDDE5-B19B-40E4-85EC-7980D8256BF7","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"fc1303d2d7b18b19e0bca3241a888b25b678dae6","datavalue":{"value":"10.1016/0304-3975(91)90354-5","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2277252$000F69BD-01E8-4F56-A39E-47D5A402B68E","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":"Q2277252$8A4B44E8-619D-448F-9498-92066062A27D","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"391107ffc7a24346d69c573e292e4ff4587e3aaa","datavalue":{"value":{"time":"+1991-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":"Q2277252$44EA62C5-762B-4095-907D-54872F8C355D","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"f280c1a866d3a96c8308679e6aaf1d3375bae7d6","datavalue":{"value":"No \\(\\Delta^ 0_ 2\\) set A with \\(\\bar A\\) and A both semilow has a minimal honest polynomial (hp-)degree. The hp-degrees and polynomial degrees of low r.e. sets are dense, showing, for example, that r.e. sets of minimal hp-degree have high computational complexity in Blum-Marques' sense. Similar results can be obtained for tally degrees and polynomial (honest) m-degrees.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2277252$5ECCC7BF-9FCD-4C90-8BF8-2BC82E925B55","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"379be2ae88ac653823960287ba517e23fc9265f4","datavalue":{"value":"03D30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2277252$9131D52B-C4F8-40C6-AF5D-46B40A8CFC92","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d7656d1c841701431b0b3d99d23720089a267cbb","datavalue":{"value":"03D15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2277252$B487700B-C5E4-402F-B28B-68CAA9F5BBFE","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"cd372216b1ecc1593db3fd1cff2596905fc63f18","datavalue":{"value":"4195924","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2277252$89702376-6B4B-4A01-8314-4057290A0949","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4ddf37f31b47a40f10efe4252a8c6b76e0c7503f","datavalue":{"value":"honest m-degrees","type":"string"},"datatype":"string"},"type":"statement","id":"Q2277252$BD869AC3-08CA-43B7-BE50-9C6CBDEB7B00","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d5134dc5571daa7c249128ceb7cff09906057c68","datavalue":{"value":"honest polynomial degree","type":"string"},"datatype":"string"},"type":"statement","id":"Q2277252$18A00752-7A2F-4EFD-9EA1-78BB00F6E8E9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a2e2a15dee7e6672a32f14d5cec64db0cc498e8b","datavalue":{"value":"polynomial degrees of low r.e. sets","type":"string"},"datatype":"string"},"type":"statement","id":"Q2277252$FE0291A3-FD53-4082-929B-DF5E2091FBBE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8894e4532f3a99a12c5483fa3f3af629bada2817","datavalue":{"value":"tally degrees","type":"string"},"datatype":"string"},"type":"statement","id":"Q2277252$36C26580-4ADD-420D-868F-A60BC39CAA00","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"2356fe1f1f6d7960e11f0114cbd6aa7fe05024f7","datavalue":{"value":{"entity-type":"item","numeric-id":247180,"id":"Q247180"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2277252$3225EBB1-F58F-4597-B481-F801A365828D","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":"Q2277252$56ED7C18-E0F7-4483-906B-F375ED4F3D69","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"fffada7472e0f9e2bb16234fab6d1ef1c9f469bf","datavalue":{"value":"https://doi.org/10.1016/0304-3975(91)90354-5","type":"string"},"datatype":"url"},"type":"statement","id":"Q2277252$548CC99C-6399-4D41-9DC6-9D8DDB60EFD8","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"89f0218914034f2ecf7603b1dfbd3fb280e2cec7","datavalue":{"value":"W2052608516","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2277252$74D0D08C-DD17-4F27-9B0D-26060D39CC0A","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"2a0199e65c145119638fa58789304520ac28cbf5","datavalue":{"value":{"entity-type":"item","numeric-id":909455,"id":"Q909455"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2277252$38499022-A7C8-477F-B34E-F4AC231C14E0","rank":"normal"},{"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":"Q2277252$8858DEF0-CEEF-4C32-9C3E-760A6A7133C2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ea45854da7df1d421d45b7aeb6b91b2908960cc1","datavalue":{"value":{"entity-type":"item","numeric-id":5537605,"id":"Q5537605"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2277252$FB3C8CD0-9BA8-461A-9DE7-7C5DCAA30288","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8163a5081f8b0b291e678042b7038ef6a2c37a8a","datavalue":{"value":{"entity-type":"item","numeric-id":4101804,"id":"Q4101804"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2277252$62932EF1-0473-4A16-A21D-BED4F5D25302","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9af52c66421185c07ca4d865efeb189c0dddc801","datavalue":{"value":{"entity-type":"item","numeric-id":1158964,"id":"Q1158964"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2277252$EA9EE833-AA70-4062-9608-E11A58E1BED4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"129b3597bf8cdce602bb595a2d31e7b6df96dbdd","datavalue":{"value":{"entity-type":"item","numeric-id":1341316,"id":"Q1341316"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2277252$3008CC46-911C-4654-ABC8-6D6527B31BDE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7cd29d8bdb9861ad9cd10e1332ef548eca3d4da2","datavalue":{"value":{"entity-type":"item","numeric-id":3705435,"id":"Q3705435"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2277252$2D06E648-B777-4B0C-ABF8-4D61750DAAED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3249023457b3007c791afda29b30dce9efc64b77","datavalue":{"value":{"entity-type":"item","numeric-id":1094875,"id":"Q1094875"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2277252$D513FAE7-039F-4838-B343-101283857A4C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6a2654c1ad3008ab65ddf962a999d4d8045dcdea","datavalue":{"value":{"entity-type":"item","numeric-id":4085242,"id":"Q4085242"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2277252$4D2DD457-ABE5-47DF-B5F2-C885D266FAB9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fe67cddb1d2e8d4582eb3ba360c56bb29576a54c","datavalue":{"value":{"entity-type":"item","numeric-id":3329452,"id":"Q3329452"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2277252$89419492-1707-43C1-8019-ECDF94BFA8BE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3ca8efb96f7e5e8c380c4a7e0ce2a99ee913ebbd","datavalue":{"value":{"entity-type":"item","numeric-id":3033321,"id":"Q3033321"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2277252$D1869460-37DD-4230-961B-9068BDA79DB8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9635365b0780328d7ae22bc69b462e7144999d03","datavalue":{"value":{"entity-type":"item","numeric-id":5573961,"id":"Q5573961"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2277252$1F7B8F88-584C-4997-9CE5-C69EDADFA177","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3a69d483c2e0de51dd3c43ba8acfd980a2417bcf","datavalue":{"value":{"entity-type":"item","numeric-id":3758245,"id":"Q3758245"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2277252$5FCAEE31-8E9C-48E0-982B-B0AC0ED75442","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8b7a79ad5d72d6b5482aaedfb2526d8e1808499b","datavalue":{"value":{"entity-type":"item","numeric-id":4185801,"id":"Q4185801"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2277252$B9562308-14AD-48A0-BD7D-14F091D9B74C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8961b4e99678ab53a0c60eebdf9c9610e0baa2b4","datavalue":{"value":{"entity-type":"item","numeric-id":4750632,"id":"Q4750632"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2277252$37E61982-68AD-4040-A2F9-AA642749BDD3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1edcfc8f162dce621803913f4363a765362e71d8","datavalue":{"value":{"entity-type":"item","numeric-id":3819052,"id":"Q3819052"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2277252$556C26E2-670B-464E-8089-0CA501E92F33","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e36959f938ab3c9135c1086302f6d3744e76b54d","datavalue":{"value":{"entity-type":"item","numeric-id":1341316,"id":"Q1341316"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"75d7af1ec947aca62efbfcf4648074e736a74615","datavalue":{"value":{"amount":"+0.8703547716140747","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":"Q2277252$489D9C32-3B2B-4C3A-BCA3-18796E3F6E37","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1ee3c09adcd8185ca6cb5d027bf441edcdcfdd89","datavalue":{"value":{"entity-type":"item","numeric-id":1201781,"id":"Q1201781"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c5b4e6c617216899e8fef454767abc74b196e0c7","datavalue":{"value":{"amount":"+0.8681936264038086","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":"Q2277252$B2A962DF-A493-4422-8910-2CD0115D286A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d3baf5bce6dc2467b5d684e9dd168ad3a181ed5a","datavalue":{"value":{"entity-type":"item","numeric-id":1094875,"id":"Q1094875"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0fa29e665c5550eb9b1cb16fd6216422e331fa15","datavalue":{"value":{"amount":"+0.8675928115844727","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":"Q2277252$9F028E0B-BA25-4B8C-B43C-03F6A3E3AC4D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7d0302878c74d10a57dc284309725440d0fe1706","datavalue":{"value":{"entity-type":"item","numeric-id":4893148,"id":"Q4893148"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0e00b28b436283f6ea1a3edde5cd04a243b0204e","datavalue":{"value":{"amount":"+0.8663607239723206","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":"Q2277252$6758E0B8-74AA-4130-97F3-69D5FB8E6E53","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fcfff5619054bd12ca32ae0ace65488f3c303422","datavalue":{"value":{"entity-type":"item","numeric-id":3781091,"id":"Q3781091"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7542e9f8c19d7c72e23d0596a183eba2bfff80e5","datavalue":{"value":{"amount":"+0.8183819055557251","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":"Q2277252$1C75BCB5-EDE0-43D2-A1B4-A36FEBB7C3EF","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2277252","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2277252"}}}}}