{"entities":{"Q809600":{"pageid":811448,"ns":120,"title":"Item:Q809600","lastrevid":64539036,"modified":"2026-04-11T20:34:01Z","type":"item","id":"Q809600","labels":{"en":{"language":"en","value":"Nonuniform proof systems: A new framework to describe nonuniform and probabilistic complexity classes"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4213442"}},"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":"Q809600$D7E6ECCD-47ED-402E-85A5-CE263151BABD","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"1fdda882561267e9898357088132b3abd61cafa4","datavalue":{"value":{"text":"Nonuniform proof systems: A new framework to describe nonuniform and probabilistic complexity classes","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q809600$C60609AF-E9B1-40A4-900D-0080FEBAF590","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"43842e3384ef369c40926067499acd06ceed1590","datavalue":{"value":"0733.68031","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q809600$AC839019-7954-464D-A465-E0EB83239433","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"c76eb8982a3075e7e7dd802e7a32bea40145627e","datavalue":{"value":"10.1016/0304-3975(91)90185-5","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q809600$6AB9D0D6-3338-47C8-81D2-51536CF64F9A","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"3ad1fe5885052ed7ad0685e302d848dc8c7cb332","datavalue":{"value":{"entity-type":"item","numeric-id":809599,"id":"Q809599"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q809600$8698E697-A9B3-430B-92B5-9696CF81AB39","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":"Q809600$74308CBC-C511-4F1D-A20F-F8E727AF8CB2","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":"Q809600$99A5BAB1-363A-4C45-96CB-FA5296EB0C4E","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"3733f0e1c5600ccc4b4b9856ab1eca7331a591b2","datavalue":{"value":"The concept of a nonuniform proof system, as a generalization of Karp/Lipton's advice classes, is introduced and studied. Many results from (nonuniform) complexity theory can thus be obtained in a unified framework. This includes certain results on probabilistic classes, lowness results, and collapsing results for the polynomial-time hierarchy.","type":"string"},"datatype":"string"},"type":"statement","id":"Q809600$17D009F4-A207-4674-8C91-9428684AABCF","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b4346faa01bb5fb0576370374d6456afd58d5666","datavalue":{"value":"68Q15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q809600$705B2771-F45A-4DB9-B697-789FEAD60F3A","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"ce7c89e41a49d7821a4c5c98012e632460475d60","datavalue":{"value":"4213442","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q809600$1B806787-FCFD-46B2-A652-8341AD9E0CF7","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cfaf02f0c561d4d48e77fb87bb5506fedded8f32","datavalue":{"value":"nonuniform complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q809600$5E43B1E4-12C9-4416-8922-7AA210FD0327","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7d3533239a13114dd574c00a3bf334d48f6ccaa8","datavalue":{"value":"advice classes","type":"string"},"datatype":"string"},"type":"statement","id":"Q809600$EF335D0F-D6A6-4A5D-A49E-3C5134E3C560","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"008c70e766fc4d68d17a2a73ce059b3504dee5b7","datavalue":{"value":"lowness","type":"string"},"datatype":"string"},"type":"statement","id":"Q809600$E697601D-796A-4F67-A3DD-57C17B894341","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":"Q809600$5924E874-5F2F-4D8D-AC4B-AA1E02559FCF","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"d89c304d2153a9624bcc7f0ccd3cdba47d29fccc","datavalue":{"value":"https://doi.org/10.1016/0304-3975(91)90185-5","type":"string"},"datatype":"url"},"type":"statement","id":"Q809600$6BAD4062-0638-48AC-BC8F-CA2E5E83E26C","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"5287317c913f865a2a0887ac1585cabdb0c8d917","datavalue":{"value":"W2021218132","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q809600$736D3DE0-525F-4435-8B94-AAF2E6DE431A","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"acaf7e392046bd492e966fb900b7bb6252c2553f","datavalue":{"value":{"entity-type":"item","numeric-id":3217605,"id":"Q3217605"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q809600$898C65BE-C90A-4492-B981-CB876A620CEE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"52939fab1bcbdd438c5cd4cb72bd03d72ac133aa","datavalue":{"value":{"entity-type":"item","numeric-id":3765251,"id":"Q3765251"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q809600$77EB4541-0E6F-4132-A6A1-196B6E890B24","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3c2468561c612bfca6312de0928b48a059a609c8","datavalue":{"value":{"entity-type":"item","numeric-id":3758244,"id":"Q3758244"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q809600$DF1DB252-875D-4660-85F8-4B9BDAA71B30","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f8ae69f8ff95a1054d345672afc2549299a932f6","datavalue":{"value":{"entity-type":"item","numeric-id":3692867,"id":"Q3692867"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q809600$3C8E0445-7EDE-469D-844E-83F8E1C23DE6","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":"Q809600$CF2063B9-0883-42CA-81E2-4A67B5026851","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":"Q809600$97955EFB-C8CF-4F2C-8A70-0FD37633547D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ca6e4b3b3a57274cdb1b75cb4c6ce319a0dbc8dc","datavalue":{"value":{"entity-type":"item","numeric-id":809600,"id":"Q809600"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q809600$ED884035-6C74-43DE-B959-9AB1BCA6918F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f6bef531e3c54b91b631aa952c0ca63f0ac7db19","datavalue":{"value":{"entity-type":"item","numeric-id":1054475,"id":"Q1054475"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q809600$F84131AD-9DEC-4C8E-AB42-20518E59873C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"40379062a2f1967b64dbc9af8fad98cd38fd1641","datavalue":{"value":{"entity-type":"item","numeric-id":1163371,"id":"Q1163371"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q809600$F12B6F25-50F6-4FF0-9AB2-6DF7F8A333F5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5b543b24a2524e76130d5c1525baa40aa9abdeef","datavalue":{"value":{"entity-type":"item","numeric-id":3675520,"id":"Q3675520"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q809600$0E1973BD-1B7C-412D-BF05-BFC6CDFDAE10","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9ec7ac9d1de9d25b673182dfb0ae85dd0acb605f","datavalue":{"value":{"entity-type":"item","numeric-id":1097695,"id":"Q1097695"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q809600$C1B8D0CD-E9FA-4299-BB3B-46B26EDF0E68","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ab289263ac80a8df854a0b026020c7e068e5240d","datavalue":{"value":{"entity-type":"item","numeric-id":1052094,"id":"Q1052094"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q809600$5A647C06-B777-4FE1-9DAA-F7C77D6E1257","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9a098647e2133258d563151bef051aaad7f30f8b","datavalue":{"value":{"entity-type":"item","numeric-id":1055405,"id":"Q1055405"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q809600$B56EDAD9-B4D2-44DE-B530-1C097C33EC94","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4a830cafef1f2c438cb7e2286bda476de992419e","datavalue":{"value":{"entity-type":"item","numeric-id":1052097,"id":"Q1052097"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q809600$0426A69A-BBF7-4DA4-B66D-1945D42DE90F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"63543c709dbc0dad9af888025f0c28158a4c2594","datavalue":{"value":{"entity-type":"item","numeric-id":802309,"id":"Q802309"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q809600$69274798-D997-4141-9B3A-A051FB8C466C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bd8421c254660c25ef5692653e4b1058bc5b58fe","datavalue":{"value":{"entity-type":"item","numeric-id":3694694,"id":"Q3694694"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q809600$1E5E6AF1-3D1D-40FA-9F5E-C8EE601CCB0D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"44ff2c269b97a88de0fe652e2add75347876b7e3","datavalue":{"value":{"entity-type":"item","numeric-id":1361890,"id":"Q1361890"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q809600$7F9E06C0-2262-48AD-B4C4-DAD87E61E918","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":"Q809600$F90C9B81-447C-462E-8DC7-8BE8B5AA833C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"37bd93f050a29505d9954e41ab03268b153e49a7","datavalue":{"value":{"entity-type":"item","numeric-id":4190619,"id":"Q4190619"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q809600$3DC6ACC8-55AC-42B4-B9F6-8094066D42AE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cd520b49bc58e84d7c227fcb0bc974b432f91cc2","datavalue":{"value":{"entity-type":"item","numeric-id":1166515,"id":"Q1166515"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q809600$25B563B1-4801-459D-A41A-F933E9ECA6E1","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":"Q809600$8562E182-764A-4823-93E0-1EA74104E9FD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4ef86d27229f88234625ab5cf631770a7bacc164","datavalue":{"value":{"entity-type":"item","numeric-id":794427,"id":"Q794427"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q809600$5716617C-C045-49D1-A739-9770D16CF7CF","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":"Q809600$F9EADA2E-4265-4B00-B002-A0F12636111A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3380ff6f4b5d07929c4c395a1faa8794b1c8021f","datavalue":{"value":{"entity-type":"item","numeric-id":3768891,"id":"Q3768891"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q809600$D158E474-A6B2-4A6F-848E-F6434582BC54","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"50e2a095ad948258628b96c48b26f673da92a690","datavalue":{"value":{"entity-type":"item","numeric-id":4725751,"id":"Q4725751"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q809600$55362CB9-C856-405B-8494-702709F0B1ED","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"836f206924c2be729daca9ee83c8b420a03b33a6","datavalue":{"value":{"entity-type":"item","numeric-id":3817612,"id":"Q3817612"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bb9407abd99706ccb4d615fb91b89f703a02b1c9","datavalue":{"value":{"amount":"+0.930873453617096","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":"Q809600$B9843241-A4CB-4DCF-B890-6C2DCDB844EA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d73ab7a481a4c957f75e2510ae09a58569abb0b4","datavalue":{"value":{"entity-type":"item","numeric-id":4621176,"id":"Q4621176"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9735ed221bb237ab19f3741798d43f74a5deed67","datavalue":{"value":{"amount":"+0.7630584239959717","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":"Q809600$92421D4E-9770-40F3-8CA7-28FF16BDE0F5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a3e46ac8440119500b204e94bdce1ef4d71d514a","datavalue":{"value":{"entity-type":"item","numeric-id":3569063,"id":"Q3569063"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a429142938562324a43378248089d640347f9a03","datavalue":{"value":{"amount":"+0.7590664029121399","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":"Q809600$7FD479A0-5DA7-419B-AE71-5CC13AAE7F0C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7c661109a2cb8100a726d1631b6278611918f0ad","datavalue":{"value":{"entity-type":"item","numeric-id":3618578,"id":"Q3618578"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b3c73d162fdd946511b27c139b85ba323074d702","datavalue":{"value":{"amount":"+0.7528907060623169","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":"Q809600$AF742AFE-4BBD-41E7-83A1-9D4612D83B99","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7ca1d4bf186a5055fb963dcacdb8efad4554212e","datavalue":{"value":{"entity-type":"item","numeric-id":3304139,"id":"Q3304139"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"84a96c9fb3cd553d6a5dc8484ff352d0b18c73ad","datavalue":{"value":{"amount":"+0.7326074242591858","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":"Q809600$4670A3EA-9A76-4749-BF24-930C9A167A46","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Nonuniform proof systems: A new framework to describe nonuniform and probabilistic complexity classes","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Nonuniform_proof_systems:_A_new_framework_to_describe_nonuniform_and_probabilistic_complexity_classes"}}}}}