{"entities":{"Q1118406":{"pageid":1129155,"ns":120,"title":"Item:Q1118406","lastrevid":42892022,"modified":"2025-07-15T18:58:27Z","type":"item","id":"Q1118406","labels":{"en":{"language":"en","value":"Are there interactive protocols for co-NP languages?"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4094816"}},"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":"Q1118406$4A70CDCD-85F0-41C8-AC97-BBF7A75BFE1A","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"8442878031f115c4a39d8f56927f53f4beec442f","datavalue":{"value":{"text":"Are there interactive protocols for co-NP languages?","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1118406$B4AE6690-4DB8-4451-AC2E-11F7C4D1EED4","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"7b8ee0552c5a74182f599c8cf3e935b86b14a199","datavalue":{"value":"0668.68054","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1118406$27840123-26C6-4322-9694-7C091CF1C66D","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"993e15379a6674e7c0ee55ff8a80f1dc13c45c64","datavalue":{"value":"10.1016/0020-0190(88)90199-8","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1118406$62F63A55-4EF5-40D8-A1F4-41F1626672B1","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"6cebb39622b69e383ce0b14ff064561e8abcf454","datavalue":{"value":{"entity-type":"item","numeric-id":1069700,"id":"Q1069700"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1118406$D7409354-C692-4489-9CD6-9AD8E49AE314","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"76fe4057f7ea6f8b50335cff0c4e37872da7faa9","datavalue":{"value":{"entity-type":"item","numeric-id":1318472,"id":"Q1318472"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1118406$26235F41-B968-4825-9487-9D38E758F86A","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"52fa7d44b58d0511cb8993765bd916aef86052d8","datavalue":{"value":{"entity-type":"item","numeric-id":63092,"id":"Q63092"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1118406$009AFD6D-CEF1-429D-B035-6F9B1E35098F","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"31a1937240ca4a323604b4728c31d242b5596d7c","datavalue":{"value":{"time":"+1988-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":"Q1118406$77F6D440-B6E3-4A56-A224-255B02C434DB","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"64d342ac5d07b146d1e8e731ac065ecfbb1c64a0","datavalue":{"value":"An interactive protocol is a game (dialogue) between an infinitely powerful prover and a probabilistic polynomial time verifier. A language L has an interactive protocol when the proper can convince the verifier to accept a strong x if and only if x belongs to the language L.    The authors conjecture that co-NP problems do not have interactive protocols. This problem is open and as hard as \\({\\mathcal P}\\neq {\\mathcal N}{\\mathcal P}\\). It is shown in this paper that there exist an oracle and a language in co-NP that does not have an interactive protocol relative to this oracle. It implies that techniques that relativize will not settle the mentioned above conjecture.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1118406$193558C6-4D6D-43E4-B051-4956E9A018B5","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"a7dde57cbaf704d564d8f981ca98d6340e3d4aaf","datavalue":{"value":"68Q05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1118406$03D2FCF8-25DA-44E0-B444-43C5B7A1A920","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1118406$DB789C72-C1A7-4ED3-900D-C927912EADFC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d7656d1c841701431b0b3d99d23720089a267cbb","datavalue":{"value":"03D15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1118406$B8A41C6B-D42F-4917-B947-22E56A3722CB","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"97bd4dab286a25edaa1fd99c155fb1280123a013","datavalue":{"value":"4094816","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1118406$60BD6257-5719-4553-B185-83629E98B635","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"31a854ebd9f451cb302334f1a143cdec8964f32d","datavalue":{"value":"co-NP languages","type":"string"},"datatype":"string"},"type":"statement","id":"Q1118406$B8CB8652-0C39-47E5-BB69-A59A797DB445","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"64d2330f317bc48b9444caf705aced9d63bab5cd","datavalue":{"value":"interactive protocol","type":"string"},"datatype":"string"},"type":"statement","id":"Q1118406$2B2BDE29-FF16-4405-9600-AFADC4681AD4","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"377196f0936f14c5f40316c205cbb7535714207a","datavalue":{"value":{"entity-type":"item","numeric-id":585662,"id":"Q585662"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1118406$BA0C1816-D1C2-40AD-8D63-60CC341C0150","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":"Q1118406$3B2A37D7-4728-4325-B1AC-271E70FB35AC","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"28d9db82f85b841635a8f838b422adf0dee67b11","datavalue":{"value":"https://doi.org/10.1016/0020-0190(88)90199-8","type":"string"},"datatype":"url"},"type":"statement","id":"Q1118406$05255A4B-35D7-4807-9535-9660619524C3","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"7a40b83d158198541f80a5c597be91c85df94ef2","datavalue":{"value":"W1982248598","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1118406$B1140A70-C19D-4778-A21A-647E2D9D0BEA","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":"Q1118406$FBCD816E-7CB8-4398-822D-3C83CE06156C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ac4b8e7cf4034c184fb2852754739a22a4e70036","datavalue":{"value":{"entity-type":"item","numeric-id":1108004,"id":"Q1108004"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1118406$2EE28DCA-64A7-48B8-8756-90CBACA87B66","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3b4feb58a2ab8f89621eb4513d36fed4a40d625b","datavalue":{"value":{"entity-type":"item","numeric-id":4365519,"id":"Q4365519"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1118406$94FA8A78-579D-419B-A6BB-44615AE2E454","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"02781992584e9d1e68b436aa02884c8182826482","datavalue":{"value":{"entity-type":"item","numeric-id":1108004,"id":"Q1108004"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8d448c48beb1f1ab8a3b45539888a455aa7962f2","datavalue":{"value":{"amount":"+0.82802564","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1118406$5CC81F82-95F5-42A1-92F4-3E0B7C298341","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a86510ae761d956360afff7921cd6aae4f801c63","datavalue":{"value":{"entity-type":"item","numeric-id":2848123,"id":"Q2848123"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e8803686601d0d633554cbe6c4fed778deccf76f","datavalue":{"value":{"amount":"+0.75299364","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1118406$C2274D82-5A8E-4678-BD7E-592C9791731C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ba77d52b3669cfcf4febac8d660405c59c9a4407","datavalue":{"value":{"entity-type":"item","numeric-id":3188271,"id":"Q3188271"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e76e824af96e5993ffe2102d5abc86e4cd1ea693","datavalue":{"value":{"amount":"+0.7428318","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1118406$8EDB6DDF-9CA7-4B1C-8C98-75BD6AEE5761","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4e04ffd61c29f005845d1b6a8e1b5778a532338f","datavalue":{"value":{"entity-type":"item","numeric-id":1898480,"id":"Q1898480"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5f1247be7fc94d6029ea87f5cd175ebf48591d19","datavalue":{"value":{"amount":"+0.73163533","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1118406$34C618B7-AEBB-4E72-AC8A-0EE57571305A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"63015037fc7d15758e49f5392a5505d616bc597a","datavalue":{"value":{"entity-type":"item","numeric-id":4409159,"id":"Q4409159"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7e12273a4e35d913ea6d727a8fa372bf16561488","datavalue":{"value":{"amount":"+0.72877026","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1118406$5C609E12-CD8C-43A8-B5A7-6B94CE4031E2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"953e66c021c2215021a40744e2201dbb6e6d6620","datavalue":{"value":{"entity-type":"item","numeric-id":1044738,"id":"Q1044738"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"71c67b348bd146c7d64a19b1c8558d1717d50cc9","datavalue":{"value":{"amount":"+0.72858816","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1118406$3E9CD69C-64F8-46CA-85AA-2415D2CA3544","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8f66a3e1d684635e05d53723d5963b71097661e1","datavalue":{"value":{"entity-type":"item","numeric-id":931434,"id":"Q931434"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8151f1a2668416a4fbd2a8a6df44edba29aaef67","datavalue":{"value":{"amount":"+0.7284976","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1118406$0194EC3A-3717-4441-A584-223AEFE7213C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dd34b354ba0e7ec60893009e6f8c85d9acb892fd","datavalue":{"value":{"entity-type":"item","numeric-id":4549424,"id":"Q4549424"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bb6d13b74ddea5f395ad180bce3317454a0c58b3","datavalue":{"value":{"amount":"+0.7239641","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1118406$7493B53E-D210-4D7E-B2DF-33780A0108C9","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1118406","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1118406"}}}}}