{"entities":{"Q813315":{"pageid":815163,"ns":120,"title":"Item:Q813315","lastrevid":56860113,"modified":"2026-03-23T21:09:13Z","type":"item","id":"Q813315","labels":{"en":{"language":"en","value":"Derandomizing Arthur-Merlin games using hitting sets"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5005125"}},"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":"Q813315$B4D1E89D-646F-430E-93B3-94C9FB3F9949","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"7e36bb942696c774c93fbbee10855c0e99962fa5","datavalue":{"value":{"text":"Derandomizing Arthur-Merlin games using hitting sets","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q813315$D30EA892-B922-49C7-A4E9-89B603092B5D","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"972061c599bd84f683ec61986034139e65ee354b","datavalue":{"value":"1085.68058","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q813315$28D0545A-EED8-4B17-9944-513279105281","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"d56a12f3874dc0f7e318148f662e38c84221f0f6","datavalue":{"value":{"entity-type":"item","numeric-id":673646,"id":"Q673646"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q813315$5C3AF003-66F6-4BE4-853C-43D8AFEC4446","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"f6692024a2326a476f00b32d78f11cab70f4af0c","datavalue":{"value":{"entity-type":"item","numeric-id":439935,"id":"Q439935"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q813315$82BFB619-7DD0-400D-9EFD-A57C4FFD9E07","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"4472b31ebff52fa964618256e5b76c8eb3e874c2","datavalue":{"value":{"entity-type":"item","numeric-id":172540,"id":"Q172540"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q813315$2D622CA1-57A6-4DDC-917C-FEB828C999F5","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"7be842e5bc1b54667cb2f669eb29d91c2f271633","datavalue":{"value":{"time":"+2006-02-08T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q813315$31F94CC3-10E3-498A-82D7-0D17D4C306EF","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b4346faa01bb5fb0576370374d6456afd58d5666","datavalue":{"value":"68Q15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q813315$2B132EC5-0691-46BB-AD74-44BE6D9DA345","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q813315$A651561F-20AC-4CDE-B0AA-B1A39695BA63","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"5fb47cf86149d03b357879abc9238ec0c624d08d","datavalue":{"value":"5005125","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q813315$AC90AB9E-7239-43FD-9D65-70F8BFBDF76E","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e6b780876d6cd571fe1e41341c135a10b0acf751","datavalue":{"value":"derandomization","type":"string"},"datatype":"string"},"type":"statement","id":"Q813315$67532243-0418-4BBB-B6D4-598483F1201E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c92ce3b2611047d0ca250e0a8d430817e1648d56","datavalue":{"value":"interactive proof systems","type":"string"},"datatype":"string"},"type":"statement","id":"Q813315$1F8ED86C-F061-4893-849E-876EF968E287","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1408da7db4c03e08918a50622f2fb337e63ab39f","datavalue":{"value":"complexity classes","type":"string"},"datatype":"string"},"type":"statement","id":"Q813315$85FAA87F-C06A-4889-B23C-8CE915F28397","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"175b06be8cd2fad00e06bef472204dbe248773bd","datavalue":{"value":"graph nonisomorphism","type":"string"},"datatype":"string"},"type":"statement","id":"Q813315$6232C804-AAC4-486F-899B-92538AD9598D","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":"Q813315$A0AC1296-9205-4876-AF1F-A6F96EE4D34C","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"025cd9c842f4b1035eaf0dbe9579a49856479653","datavalue":{"value":"https://doi.org/10.1007/s00037-005-0197-7","type":"string"},"datatype":"url"},"type":"statement","id":"Q813315$5F4A27C0-E6C6-4ACC-9FA4-A29C5728277E","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"3848760c5f842ade56bc8e758fb254d02dc3832c","datavalue":{"value":"W2098324348","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q813315$397D588A-EAAA-4EBB-8D8F-569935F79195","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"3991c2d89032de7fe42626e99dc04a3e4008cac1","datavalue":{"value":"10.1007/S00037-005-0197-7","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q813315$22C14FB1-2A30-4837-A3E1-B78D096519D0","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e05f5ce8501b89ede81fdea11dcd89752a6f76b6","datavalue":{"value":{"entity-type":"item","numeric-id":4472503,"id":"Q4472503"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0a9c3628304a26f1d4b3049e5e5453cf52d12600","datavalue":{"value":{"amount":"+0.94302475","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":"Q813315$095171EF-88BC-4ADF-8E4D-2C4FCF40C74A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2c920e7b191a07de1ff82fb439b4803631188054","datavalue":{"value":{"entity-type":"item","numeric-id":1601037,"id":"Q1601037"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0a9c3628304a26f1d4b3049e5e5453cf52d12600","datavalue":{"value":{"amount":"+0.94302475","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":"Q813315$EE0A0917-67EB-4578-8377-5ABBC538548A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b8326fa50fdbdc26a99c1bea1490a855b44143e9","datavalue":{"value":{"entity-type":"item","numeric-id":645124,"id":"Q645124"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"eb154b9425a6e9e6d167db2b544c784d2befe7c2","datavalue":{"value":{"amount":"+0.904315","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":"Q813315$2D42F0A0-E63D-42CA-A147-DD102C61D0A6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b9d7bda51f6e227e7033f5e00f784ec8e74721cf","datavalue":{"value":{"entity-type":"item","numeric-id":1762663,"id":"Q1762663"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0437d6fef76c9ac9a0f1f478731fd62c6eff823c","datavalue":{"value":{"amount":"+0.8901645","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":"Q813315$0015E40B-EEA3-48C1-A7B5-97DD67320B9E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"beabc76344ab3768eadb52088932d1448a91824a","datavalue":{"value":{"entity-type":"item","numeric-id":1106840,"id":"Q1106840"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fc756fd1fded2cf11e2a82da751f1c0b6aef5f63","datavalue":{"value":{"amount":"+0.8813689","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":"Q813315$DB1AA3F8-A988-4286-99D9-C8C13ED1238E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"75bc27198181e802b8c7abc6552f4eaf5dbe1820","datavalue":{"value":{"entity-type":"item","numeric-id":5714674,"id":"Q5714674"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"651e1ca9b41cb92d0949af9e2730db9360a93285","datavalue":{"value":{"amount":"+0.87881434","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":"Q813315$26C6A5FF-C21D-47DF-955D-654CF54126EF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ca15eb8662b0748e09b81fb52482afed38dea4df","datavalue":{"value":{"entity-type":"item","numeric-id":2012178,"id":"Q2012178"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d39e949e02e6151cab6ee622987f47200a717237","datavalue":{"value":{"amount":"+0.8593874","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":"Q813315$49C4525A-D944-4A0F-B7C4-F8471581A3D1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0686a95f62dd29c05c3d4f51c69729ccc69225e0","datavalue":{"value":{"entity-type":"item","numeric-id":468727,"id":"Q468727"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5b761dbfb0bfc30111a3fd2db87d7398f10cb34a","datavalue":{"value":{"amount":"+0.8479732","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":"Q813315$C71AFEA6-8B29-4D70-9535-F15F6501F29A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6d2c74ee8df8ba103fadefe3d6c6b1f927ad4482","datavalue":{"value":{"entity-type":"item","numeric-id":1961380,"id":"Q1961380"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8c6b044ef7ca2e2feba4c2461200320bddde845b","datavalue":{"value":{"amount":"+0.8458143","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":"Q813315$9A1D9C32-0F9F-4507-A6A7-29EB1F9CE957","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2d755d3157bb2af50ed779c2adb1ae088d6c3fb6","datavalue":{"value":{"entity-type":"item","numeric-id":4258571,"id":"Q4258571"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8c6b044ef7ca2e2feba4c2461200320bddde845b","datavalue":{"value":{"amount":"+0.8458143","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":"Q813315$058E55C7-4C87-45B4-A8A9-7C9795DA4E3A","rank":"normal"}],"P163":[{"mainsnak":{"snaktype":"value","property":"P163","hash":"bee1ddd2bb542a0e64ca96574e4fab1bba361385","datavalue":{"value":{"entity-type":"item","numeric-id":57074,"id":"Q57074"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q813315$3C018F7B-9002-4592-84DB-392AA42DEE8F","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:813315","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:813315"}}}}}