{"entities":{"Q2638771":{"pageid":2649514,"ns":120,"title":"Item:Q2638771","lastrevid":49453459,"modified":"2026-01-07T04:42:27Z","type":"item","id":"Q2638771","labels":{"en":{"language":"en","value":"Relativized counting classes: Relations among thresholds, parity, and mods"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4182810"}},"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":"Q2638771$036A25AA-CA89-4CAF-B490-E4AC71CFC8CF","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"3fb5d155b1d37836f8d9493e15633e47f2890966","datavalue":{"value":{"text":"Relativized counting classes: Relations among thresholds, parity, and mods","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2638771$9D6D7267-0E8E-43E5-9AD7-1256C8866294","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"10aef6bd22d979d56ec1c5497771f729a590a8eb","datavalue":{"value":"0717.68031","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2638771$D0C2D0AF-5EE0-43BB-967A-1440398F2264","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"8c3a7a9a155f4f89fae19e3c53c197c07365cca7","datavalue":{"value":"10.1016/0022-0000(91)90040-C","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2638771$CDDFFAC1-888A-44FF-98B3-A506FCC5CE48","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"0353358515be2d1b5877a1b267862980a7b952cd","datavalue":{"value":{"entity-type":"item","numeric-id":294935,"id":"Q294935"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2638771$89AA5885-2F4A-4C31-81E7-5B4D30E971AD","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"3340243f57e05f2265c56423c388055a14b114fa","datavalue":{"value":{"entity-type":"item","numeric-id":107189,"id":"Q107189"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2638771$EDF57E5D-D4E1-4DE5-AC73-C0EC2E05D169","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":"Q2638771$8355F65F-E743-4E84-A61D-F8396396E434","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"8e2749a0fab1e69c6dff4f5ebd522959db8f210c","datavalue":{"value":"This paper brings a contribution in so called structural complexity theory which is trying to separate some known complexity classes or to show at least that the relation between some complexity classes will be hard to establish. The relation between two complexity classes A and B is hard to establish when exist such two oracles C and D that \\(A=B\\) relativized through oracle C, and \\(A\\neq B\\) relativized through oracle D. So, ``hard to establish'' means that the classical techniques like simulations or diagonalizations cannot be used to establish the relation between A and B. It is shown that the relations among several classes laying between P and PSPACE are hard to establish. Most of the complexity classes considered are defined by a modified acceptance of nondeterministic Turing machines.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2638771$CCBC1AB7-D7D4-4F80-B85A-BF6CA165AA0C","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b4346faa01bb5fb0576370374d6456afd58d5666","datavalue":{"value":"68Q15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2638771$E125E072-50B6-4DE1-8301-01E62AB50D00","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"35bbdcbda53152c249a7f99650e19b5ef62999f2","datavalue":{"value":"68Q10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2638771$73080D27-86EB-44B5-9B7E-97713F2F79A1","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"045f618f51dad92ccae82ef1b2dafd6865956907","datavalue":{"value":"4182810","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2638771$DDABABEE-0647-475E-96CC-403809D1B8AF","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ac873341ab34d6db98676ef037e18583cae25841","datavalue":{"value":"oracle","type":"string"},"datatype":"string"},"type":"statement","id":"Q2638771$D1C04E8E-6869-401E-A6F0-988E2C5D2583","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f8d07e6fe9a0ae20e46d65e16ae284315735a2df","datavalue":{"value":"relativised complexity classes","type":"string"},"datatype":"string"},"type":"statement","id":"Q2638771$F6BC84B4-C748-4381-876F-0373FA214DDA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"96b99193434b160c0229142e122a12419e6dec02","datavalue":{"value":"separations","type":"string"},"datatype":"string"},"type":"statement","id":"Q2638771$66EAFBBA-85A4-4DE1-B685-369F4073D7FA","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"633fdcabf2e644e3cc3929da0924cb1d112f41ed","datavalue":{"value":{"entity-type":"item","numeric-id":208754,"id":"Q208754"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2638771$023C84F3-90AC-47BA-A9F3-CBC71685DDF0","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":"Q2638771$13A6A56C-99FE-4144-BCFE-008651ED7576","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":"Q2638771$BEB0FB59-CFF0-4F83-80B3-52FC34E9C038","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0fda5ce3f0ebf248a51aaaa608f3b42b80365836","datavalue":{"value":{"entity-type":"item","numeric-id":5896571,"id":"Q5896571"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2638771$7CB9C161-A095-4527-9FC7-6EC4E56FB65C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"54e3771f8171656e0aed45bf0777afe8aad7a3a9","datavalue":{"value":{"entity-type":"item","numeric-id":3902480,"id":"Q3902480"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2638771$4CBF0885-3D39-4E1E-BC55-E8539B03987C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c317ee9b89d25866849eff84487be5a7c7991b60","datavalue":{"value":{"entity-type":"item","numeric-id":3331209,"id":"Q3331209"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2638771$E446B98E-0EF5-4A04-BC94-47FF87F38A5B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"51e8ca4fe98e898ca79eea259b27eebc5567af3b","datavalue":{"value":{"entity-type":"item","numeric-id":5096157,"id":"Q5096157"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2638771$5D15728B-4C0A-4B28-88C8-6124224837FF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"836ad2a04f82225da478ca9f694f5cd99360b315","datavalue":{"value":{"entity-type":"item","numeric-id":4198056,"id":"Q4198056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2638771$6B280E24-7F26-4FAF-B8D0-05BFB35F8D16","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7eb24dff4005148539085ff5c885035cfccaed69","datavalue":{"value":{"entity-type":"item","numeric-id":4140967,"id":"Q4140967"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2638771$4E1258D4-FEC3-4EB7-A6F2-1A69DF7A64E3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f6690941b790d3f730c7ae6b7e325ad8391f2459","datavalue":{"value":{"entity-type":"item","numeric-id":1083204,"id":"Q1083204"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2638771$AF114437-4CD6-4898-AC73-CD996B418812","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dd07bc9a9b69ce8a80cf38ac60dbedf570ebf67d","datavalue":{"value":{"entity-type":"item","numeric-id":1109566,"id":"Q1109566"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2638771$0E234C65-85FC-485B-829C-C91418FD7176","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"adc67edbb1677ad77489d6c17db913a838f0b011","datavalue":{"value":{"entity-type":"item","numeric-id":3696516,"id":"Q3696516"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2638771$AADB9193-BCEB-49E9-852A-EC850FE2E641","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f0b28f4e63e0fed9ced8619416c685ca7379b32b","datavalue":{"value":{"entity-type":"item","numeric-id":3996586,"id":"Q3996586"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2638771$9FB2398E-2251-4E3F-A6E8-E4E0DE9B9802","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9fb2c936121f4f1d6e6f7ab70089a797e73426bb","datavalue":{"value":{"entity-type":"item","numeric-id":3662618,"id":"Q3662618"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2638771$A3DFD29E-D44A-4174-89AF-E330A5E9D99D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e4751cb99cfb27abec44f2378f8165a3a9a6376a","datavalue":{"value":{"entity-type":"item","numeric-id":1236109,"id":"Q1236109"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2638771$8DEDF4E4-E5F4-4393-8F0B-28533C8E1F8D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"68c516460706e34bfacf776c096f40a576fd2116","datavalue":{"value":{"entity-type":"item","numeric-id":600247,"id":"Q600247"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2638771$49973EA2-E7E2-4FB9-9D62-EA57C48F67BA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a0e1c59b20b978e8e0de5a32fdeb6c212dbd6e1a","datavalue":{"value":{"entity-type":"item","numeric-id":1090455,"id":"Q1090455"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2638771$6DC2DC51-79A1-440C-A1B6-E838789DD68F","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"3b1ea40fc3b7f4d3d5480121d6d337496f7f748b","datavalue":{"value":"https://doi.org/10.1016/0022-0000(91)90040-c","type":"string"},"datatype":"url"},"type":"statement","id":"Q2638771$E9FB8F13-03B3-4AE7-89D7-D9A78C1D0393","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"d73e5c083fcf97dda0e5a508e7d85dad25b0c2d3","datavalue":{"value":"W2002323159","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2638771$98812766-147A-4C97-B4FF-5916A9830797","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1bc660cbae522e2a7737a5a8806145cca1880842","datavalue":{"value":{"entity-type":"item","numeric-id":4302854,"id":"Q4302854"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"508901efa1f8bc0fc50399f88b75b8dbd6d30a77","datavalue":{"value":{"amount":"+0.812717616558075","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":"Q2638771$86C4103D-DAA8-4B31-8C7A-6979F67082C8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ca23cec0135d3e9a8f38040ca062aacb68d3fd92","datavalue":{"value":{"entity-type":"item","numeric-id":5905584,"id":"Q5905584"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"40efae1e59e064028fdfbf97efdf76191db0be48","datavalue":{"value":{"amount":"+0.8089189529418945","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":"Q2638771$E0A6B5C7-AB73-4298-A1A8-6BFF17AEBBDA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9f76f81974ece2cd529677275a089ee1ebb5998f","datavalue":{"value":{"entity-type":"item","numeric-id":3805899,"id":"Q3805899"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"75e4ed78eed78f8653dc67e9d5da7ee0806b5291","datavalue":{"value":{"amount":"+0.8085947632789612","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":"Q2638771$CCADBE27-D5A9-4F64-8FB7-CCA27E490D63","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"db4a30c2739a0b26d2b5fd766fc4332be5436ce1","datavalue":{"value":{"entity-type":"item","numeric-id":5896571,"id":"Q5896571"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"197d07c29c7e1a1aa979ab2cab7a17e0622840da","datavalue":{"value":{"amount":"+0.8016853332519531","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":"Q2638771$60715F05-A860-46B5-9CE9-BE2DB13FE20A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c9afc7d3171fbb8842cffe7ea910a6b196e67baa","datavalue":{"value":{"entity-type":"item","numeric-id":3779736,"id":"Q3779736"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ef572188151dca026b81a4dac6752c94dacbcc9a","datavalue":{"value":{"amount":"+0.7971327304840088","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":"Q2638771$97A9AD4B-C69D-4E0B-B365-0E8914FE19F6","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2638771","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2638771"}}}}}