{"entities":{"Q794427":{"pageid":796275,"ns":120,"title":"Item:Q794427","lastrevid":48715450,"modified":"2026-01-05T17:01:56Z","type":"item","id":"Q794427","labels":{"en":{"language":"en","value":"Some consequences of non-uniform conditions on uniform classes"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3860384"}},"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":"Q794427$F226538B-B707-470C-BAAF-5F2572E8D9E7","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"57c4fc39dce1f2d8e4064a43307f6c46a296be57","datavalue":{"value":{"text":"Some consequences of non-uniform conditions on uniform classes","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q794427$D40ABFF7-5FC5-4041-982F-A0F041F00245","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"c381f1096ee1e0d900bb4ab47740b414aa8d20f4","datavalue":{"value":"0541.68017","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q794427$24788274-DA3D-4151-A833-1F931997EEE3","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"9e1ecc12abbed04dd74f714a11d3542c6f4bd0d0","datavalue":{"value":"10.1016/0304-3975(83)90020-8","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q794427$C10CBC41-4C4E-4F80-A5E6-318D0C3CA0DB","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":"Q794427$6ABF2311-8EBB-48D3-81B3-354B04213111","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":"Q794427$ACAC24F4-C994-40BE-9BD0-690D8A094856","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"21a998bcc733caac0bc203d84959c41ea0d0a057","datavalue":{"value":"Non-uniform complexity classes appear from the circuit complexity. It is proved that if non-uniform classes \\(\\Sigma_ i/poly=\\Pi_ i/poly,\\) then \\(\\Sigma_{i+2}=\\Pi_{i+2}\\) in the Meyer-Stockmeyer hierarchy. Apart that, some connections between coincidence of complexity classes and sparse complete sets are ascertained. If there exists a sparse set which is complete for co-NP relatively to conjunctive reducibility then \\(P=NP\\). Besides that, if NP is conjunctively and disjunctively reducible to a sparse NP-complete set then also \\(P=NP\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q794427$6538AF31-9B10-45EA-BC72-50535DA276A4","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q794427$97CC1DD6-422E-468D-9714-1B580BE6DC60","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d7656d1c841701431b0b3d99d23720089a267cbb","datavalue":{"value":"03D15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q794427$7EFC3071-C84A-4450-839E-01D94DAAFB85","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"a16fe9d1dcc317e520b1c645f8acd28d8218afa8","datavalue":{"value":"3860384","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q794427$9EAB59F6-00E6-4E7A-995D-202FC4AFAC93","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"71accd3f7108f73d599fa3d207930bd93da29827","datavalue":{"value":"Non-uniform complexity classes","type":"string"},"datatype":"string"},"type":"statement","id":"Q794427$D0000DB3-1003-41A5-86C7-F2A1EEA33625","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ebc5ac139429a7d7f2ed52088dc73bb6dde0bbde","datavalue":{"value":"Meyer-Stockmeyer hierarchy","type":"string"},"datatype":"string"},"type":"statement","id":"Q794427$D88A2309-C8B6-4AE8-956F-EA6336A2637C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5b9d868a2063d15cbc5545d9ca7928353602414d","datavalue":{"value":"sparse complete sets","type":"string"},"datatype":"string"},"type":"statement","id":"Q794427$3F874F3E-A976-4E10-B047-9D3179D6B9F3","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"d871c1b75fb83a30076e692713ffd500de027eb4","datavalue":{"value":{"entity-type":"item","numeric-id":676576,"id":"Q676576"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q794427$77941850-8463-4BD3-8BF5-CA7D15684E49","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":"Q794427$B4C5BE81-5141-4A5F-8010-5E23612468FF","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"8800f955e4bd5fff4eab61f11d6e0ca242881cf6","datavalue":{"value":"https://doi.org/10.1016/0304-3975(83)90020-8","type":"string"},"datatype":"url"},"type":"statement","id":"Q794427$53501321-9918-4307-9881-80E0CE89592B","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"604fb7e96bcb7f99d88cc96a24a55582c7ddd75c","datavalue":{"value":"W1986602165","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q794427$E6C85AAF-C1F1-4F4C-BA96-C3327CA6DEA8","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"b4553a412b4b55bb167272479a5aca159281f2c2","datavalue":{"value":{"entity-type":"item","numeric-id":4160434,"id":"Q4160434"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q794427$E4AA4488-E778-4A46-8760-8E921FC0B5CF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"45543575358fa9f936229ea1980f01498db37989","datavalue":{"value":{"entity-type":"item","numeric-id":4128010,"id":"Q4128010"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q794427$B46BEB52-BE65-462B-AAAA-25D1AAF80BF4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7cd3656cf316bb6b47d075cb851e6ca065390824","datavalue":{"value":{"entity-type":"item","numeric-id":3051374,"id":"Q3051374"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q794427$91D39CC6-0C04-4DEB-B0E2-308E45F9B943","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c7d15acf9b2dc594da15dc289088a8a93d59b4f8","datavalue":{"value":{"entity-type":"item","numeric-id":1223166,"id":"Q1223166"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q794427$088EC74E-099E-4082-AED4-50F8BDD52956","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":"Q794427$93CC959B-EABB-400C-AC96-0F369EF60324","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c6c4e86478056d66da69114455db65432b30398a","datavalue":{"value":{"entity-type":"item","numeric-id":3314997,"id":"Q3314997"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q794427$CF570445-6F2F-4263-88B2-A54D4A427A9B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2a6cda79edbd7844280d7256f6bebd6ec8725739","datavalue":{"value":{"entity-type":"item","numeric-id":3335768,"id":"Q3335768"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q794427$7DFD9F90-C18E-4022-A8D0-61A7662269CF","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6ce60a7b12a52d81f977c6807db10402fac1fae8","datavalue":{"value":{"entity-type":"item","numeric-id":4256649,"id":"Q4256649"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3116853cf489c207d5178bf4c8170e3e89042f2a","datavalue":{"value":{"amount":"+0.8131147623062134","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":"Q794427$8379C07C-A2B4-4D88-9D70-4BB824CD92D4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1d2c6b00319aebd8229b2a325bdd25c903fad5ba","datavalue":{"value":{"entity-type":"item","numeric-id":3314997,"id":"Q3314997"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5d418b3fde246de101d603d5e081f3a59fa7f16f","datavalue":{"value":{"amount":"+0.803558886051178","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":"Q794427$DF5ADA41-CCEE-4E8A-85D8-F59F0E7C9880","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0d99b28e01d90fb9e4a8b0ef44d9dc319ef37024","datavalue":{"value":{"entity-type":"item","numeric-id":3812229,"id":"Q3812229"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"21b87e8f8ecfc148903292fdf5ba12f8a4d11fb8","datavalue":{"value":{"amount":"+0.8011518716812134","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":"Q794427$815B6F4C-6A4F-462A-B348-5331EE3F72D3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4c2adc893ba0e353cc07a8405075284e7651ff53","datavalue":{"value":{"entity-type":"item","numeric-id":3335768,"id":"Q3335768"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"930bbc0b24a1b6e304dbe9ee45a51cb1348cbebe","datavalue":{"value":{"amount":"+0.8003726005554199","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":"Q794427$E49A8320-485A-44C1-ADFD-F7B7CB7656FC","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":"09e11613588fdef5eda8529fdff29961de2d88ce","datavalue":{"value":{"amount":"+0.8001010417938232","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":"Q794427$CBF8DDDB-6529-4C26-A975-E18A246AAFFA","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:794427","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:794427"}}}}}