{"entities":{"Q896677":{"pageid":898525,"ns":120,"title":"Item:Q896677","lastrevid":65170488,"modified":"2026-04-12T00:47:04Z","type":"item","id":"Q896677","labels":{"en":{"language":"en","value":"Positive and negative proofs for circuits and branching programs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6519454"}},"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":"Q896677$CAC82530-787B-4168-8393-33973B35EB4E","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"3ee7c35f5bbe8eaddba366c28c6fbb52dd8cd4e9","datavalue":{"value":{"text":"Positive and negative proofs for circuits and branching programs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q896677$BA610A59-ADC1-4702-A3D8-A900854801D5","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"550d54b2652e3ca4baaf95a7d62ba132f7fc8d92","datavalue":{"value":"1347.68158","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q896677$953FFB8B-E35D-4DEF-9DE6-8DBAB7F5B0AA","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"b8a528bd6d542930e9063892faa470ea596c53b2","datavalue":{"value":{"entity-type":"item","numeric-id":896674,"id":"Q896674"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q896677$EE5B3B08-54C0-4275-BE1E-3F65ECA87347","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"1a0f05b8d8ab5df81592e837ec323b1c7b0982c6","datavalue":{"value":{"entity-type":"item","numeric-id":896675,"id":"Q896675"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q896677$76171664-986D-4F13-9D18-6D44068974E4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"2544a2aff544dc84ffd23bad61458f6d1fd945ff","datavalue":{"value":{"entity-type":"item","numeric-id":347113,"id":"Q347113"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q896677$454BEFE2-63F1-4FF7-BD7B-0F3C223ED7C4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"f60fe030e6054c5ae924fab6fd04a4a649505e1a","datavalue":{"value":{"entity-type":"item","numeric-id":896676,"id":"Q896676"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q896677$55B87242-CBBD-401F-9A06-7AFAE9D7A3FD","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":"Q896677$1A39DFE7-7E13-4C6C-BB9D-0AAD0ADD1A08","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"b6e0062212bbfa3dc4430f2b4b6e15b88e23b47c","datavalue":{"value":{"time":"+2015-12-10T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q896677$3540A42A-8BD6-473B-920C-457CB72D3477","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"a871f0de97042529233a7ff90bd445c997d45d21","datavalue":{"value":"The authors think that the negative proofs are a neglected aspect of counting. They introduce the notion of negative proof tree. Based on some complexity class C, Zap-C is the class of functions counting positive and negative proofs.  They prove that Zap-BWBP \\(\\subseteq\\) Zap-NC\\(_1\\) \\(\\subseteq\\) Zap-PBP.","type":"string"},"datatype":"string"},"type":"statement","id":"Q896677$C13B8E6A-8DB9-495D-A56F-6AEBCE02C94A","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"be9b7bf9cd273aeaf91ec2e38cce549e5afc8f07","datavalue":{"value":{"entity-type":"item","numeric-id":192024,"id":"Q192024"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q896677$72B0E15A-9DE2-4DA4-8FA7-4AE0D626D882","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b4346faa01bb5fb0576370374d6456afd58d5666","datavalue":{"value":"68Q15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q896677$B09DA481-4AD7-4CD6-923F-EFC68DF46AC4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d7656d1c841701431b0b3d99d23720089a267cbb","datavalue":{"value":"03D15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q896677$5F98351B-6508-429B-8A6D-88A7767FA0F9","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"585ec6ae334713b51ea9ef5f4c2b9bbf050e22ce","datavalue":{"value":"6519454","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q896677$C10D971E-AB9A-44B4-B8B1-4CDA00B548FC","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0c2773dc0449ebf96bb1747bc4f2b2f0a2faa889","datavalue":{"value":"circuits","type":"string"},"datatype":"string"},"type":"statement","id":"Q896677$8981351C-C49A-4222-AE1F-20EBEE9B4354","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"aa64eae916ac50f9d0bdde79696d641a11ea4cba","datavalue":{"value":"counting","type":"string"},"datatype":"string"},"type":"statement","id":"Q896677$5AAFA97C-78ED-47BE-9C9A-7586950E084A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fc86f63fe1098dbc31c9ce39bff3551b474b42d9","datavalue":{"value":"arithmetization","type":"string"},"datatype":"string"},"type":"statement","id":"Q896677$9EEB27AE-C237-4721-92D2-8CFE37DE87F6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d7f0782873eb704bb82a23c2f958eb362c63bc36","datavalue":{"value":"number of positive proofs","type":"string"},"datatype":"string"},"type":"statement","id":"Q896677$5BE21333-D783-4AE6-BFF9-62C72E84C24C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4e7a1b4f244b9fd40d54501746ea95dcb762daf0","datavalue":{"value":"number of negative proofs","type":"string"},"datatype":"string"},"type":"statement","id":"Q896677$F33A4AFF-0827-430F-ACB5-B8291DA55DF2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ec24897927a0742784fae89aed9a922bc2a81fec","datavalue":{"value":"branching programs","type":"string"},"datatype":"string"},"type":"statement","id":"Q896677$29CE5E61-3D01-4CC0-9EEF-4605DD6AEEAC","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":"Q896677$B8AA0227-BCEB-48E7-9950-2689DD4FAAF4","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"caceae3d4368257300fceca7d8dc0b792f5446fe","datavalue":{"value":"https://doi.org/10.1016/j.tcs.2015.08.041","type":"string"},"datatype":"url"},"type":"statement","id":"Q896677$CC2F6EF0-55C2-4BB0-AD74-CC74602914B8","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"a530383d50ff18fae49f1d0847fc665af4517b3a","datavalue":{"value":"W1789118945","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q896677$510F76E3-2581-4B12-8306-0C9CE7709A9F","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"aaee5992bec02cd5037102dcf658e53f9a67bdb7","datavalue":{"value":"Q113863214","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q896677$7BA2579B-2413-46BD-B59C-FF8B719A8CA0","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"f8897f49b078c83cd92c803ad95e3fa289682920","datavalue":{"value":{"entity-type":"item","numeric-id":5465356,"id":"Q5465356"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q896677$D8B314A3-9B51-4414-BF73-23227496EB09","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"85332f45c574807884e55f6488cd3b450f276a8f","datavalue":{"value":{"entity-type":"item","numeric-id":1117696,"id":"Q1117696"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q896677$20DC5022-01A6-4FD3-B736-2F41CB730B5B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f1dfb43ddba5fcd921bc27481c33f3a5541a41d0","datavalue":{"value":{"entity-type":"item","numeric-id":1276170,"id":"Q1276170"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q896677$689FB234-C83E-4C74-96C8-015AFA2ADCDF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9b016e3db755039e61ff453c3ed444a58cc677de","datavalue":{"value":{"entity-type":"item","numeric-id":1318473,"id":"Q1318473"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q896677$E953362F-7064-462F-B381-96A70EDA6557","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f306656afe91eb6eb114c167fa6877d275da46f2","datavalue":{"value":{"entity-type":"item","numeric-id":2432526,"id":"Q2432526"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q896677$253C9DFE-AB64-413B-BAE5-C29B0460D94B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"80c767919e94a3332b8d198174b1921d5e4026fe","datavalue":{"value":{"entity-type":"item","numeric-id":3821586,"id":"Q3821586"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q896677$0901B13B-7AF8-49CA-9F14-F86ED3C2D532","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"92ca15ef75a0fb7f15929b5311b86427bc0cdd77","datavalue":{"value":{"entity-type":"item","numeric-id":3691587,"id":"Q3691587"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q896677$2EDBB7A6-D7B2-4F08-8DFB-CE98C9F9EFCB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b6bffcdd91714eea88413e9d8afc16ac428a2fda","datavalue":{"value":{"entity-type":"item","numeric-id":1208408,"id":"Q1208408"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q896677$A94F259C-3C4E-409D-898C-3CC7253E951A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3479b1b8ce1eb8a8699c52a172d26d4d947366b0","datavalue":{"value":{"entity-type":"item","numeric-id":4298260,"id":"Q4298260"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q896677$7980CDA1-B3CE-4ACA-B744-85E0E50ED677","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fbff024c016734ad1d82811c75ff1a00031085a6","datavalue":{"value":{"entity-type":"item","numeric-id":4943859,"id":"Q4943859"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q896677$A0D9BF9E-407C-4339-B574-937985C241A6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"186efa9cbcaad91d0d4ad1f36de56ca7d39bfe2e","datavalue":{"value":{"entity-type":"item","numeric-id":1099620,"id":"Q1099620"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q896677$1FEFCA05-4F89-4271-882D-2EDCFC2D81C4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"188e8b5f1d43587af358c4df8923be0da414f307","datavalue":{"value":{"entity-type":"item","numeric-id":4016401,"id":"Q4016401"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q896677$2A09227A-F1DA-404B-A22C-4131A4D8EFFC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"624abf0da839d476906101af8b6d74820b65cb0e","datavalue":{"value":{"entity-type":"item","numeric-id":4393484,"id":"Q4393484"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q896677$BDF9096F-7B81-4135-B87B-E00CAA091978","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5a875fce30fed92bb3f3cd4f320227a2704f1c51","datavalue":{"value":{"entity-type":"item","numeric-id":3835026,"id":"Q3835026"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q896677$F9429E4B-79AD-4671-B5C6-C741873D06B8","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"9d220cc8c7c4952543470ea04f22d8c5410f8509","datavalue":{"value":"10.1016/J.TCS.2015.08.041","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q896677$A91B9A81-A87E-4788-AC53-61FA0C1B43D3","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d1ec16d3363d51d6df70392926a7a449b67e8805","datavalue":{"value":{"entity-type":"item","numeric-id":5496195,"id":"Q5496195"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"394cc19d5b2cad5c96e113b2520781535b665183","datavalue":{"value":{"amount":"+0.9710657000541688","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":"Q896677$C62FDE21-DB7D-47BF-8141-41A2CEB61199","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"79771563fb9c1f0eaf03a19599ba96dd8621d354","datavalue":{"value":{"entity-type":"item","numeric-id":4503939,"id":"Q4503939"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cb4b45da98322dc6df354d00888fddc4af4fedbb","datavalue":{"value":{"amount":"+0.7518438696861267","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":"Q896677$4933CDEA-28E9-489E-B2A4-D07A4D1A67A3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c5384dc44e84550767d9c575f4d43e9ce5672d59","datavalue":{"value":{"entity-type":"item","numeric-id":1961372,"id":"Q1961372"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"13c315dd7f1cc0f4970160a8d13ae57c89711bcb","datavalue":{"value":{"amount":"+0.7363713979721069","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":"Q896677$F4BA5B1B-F952-4893-B3DF-DBECFE0D1930","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"200cdefd35834d0943aecd2a4060f1ce0f630ff0","datavalue":{"value":{"entity-type":"item","numeric-id":1405787,"id":"Q1405787"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ef415345d5407d79eeabacc4c70bf130e7e768c5","datavalue":{"value":{"amount":"+0.7140756249427795","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":"Q896677$F8858046-E984-4B9C-AC99-0B7B72E3DDFE","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":"b640749c54441edaa718e8b4fed48049223c061d","datavalue":{"value":{"amount":"+0.7113940715789795","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":"Q896677$E9C25B74-284F-464D-A7EE-DE59F6EE07E8","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Positive and negative proofs for circuits and branching programs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Positive_and_negative_proofs_for_circuits_and_branching_programs"}}}}}