{"entities":{"Q674343":{"pageid":676192,"ns":120,"title":"Item:Q674343","lastrevid":63487239,"modified":"2026-04-11T13:29:56Z","type":"item","id":"Q674343","labels":{"en":{"language":"en","value":"If NP has polynomial-size circuits, then MA=AM"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 986075"}},"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":"Q674343$A0195F55-4DF1-4835-B88B-3221A9200DCD","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"b2ed62beae1873fa2ce89dd558582e7e5d4d4774","datavalue":{"value":{"text":"If NP has polynomial-size circuits, then MA=AM","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q674343$2D202EC5-C038-45B5-8266-BC5A1D761CA3","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"36130a3aa783993486b4526ed43d3fbaa70bd538","datavalue":{"value":"0874.68185","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q674343$F713C3F1-5AC6-4192-93BD-C41583B09FE0","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"9ca035f5daa79533fe333b33edb8d5a2b4c3071f","datavalue":{"value":"10.1016/0304-3975(95)91133-B","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q674343$DE28AC10-212F-4F74-B8A2-008438C7806D","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"dd4aeb4e5a3ca371ed6df12fa17daeace8cca68f","datavalue":{"value":{"entity-type":"item","numeric-id":197718,"id":"Q197718"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q674343$F89106F8-E046-441C-9ABA-E99D47C5436C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"1ccdbbd400f0c973fa2e979fe6e13986f59d9284","datavalue":{"value":{"entity-type":"item","numeric-id":259078,"id":"Q259078"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q674343$0C30ADED-F637-4986-A018-BCCC5ECD8F65","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"94ed31c214c2e46155e46804659cfb6e6a2b1fbf","datavalue":{"value":{"entity-type":"item","numeric-id":598181,"id":"Q598181"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q674343$2E7DE7AB-4C28-4400-95C5-1908DA799037","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"98e020d336f4040f2344877fb27890751f480383","datavalue":{"value":{"entity-type":"item","numeric-id":1052096,"id":"Q1052096"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q674343$E37BC3C7-1B7F-474E-ACED-8987E1467FDC","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":"Q674343$DB787FCF-7FA7-4B32-8CAC-C2ECF90EB934","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"00d109e26a7fcb906853bbbede91db350c2b0258","datavalue":{"value":{"time":"+1997-02-28T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q674343$A09638BB-C8F6-434C-BEEA-C9B3D703FC70","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"40d293f5d2161e80872b42afb12a3fc45e5d1401","datavalue":{"value":"68Q55","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q674343$71446FF4-0C73-4F91-A261-3DB5C8487037","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"77b8150d4d6a12417b136606d02442b8c2ac7ac8","datavalue":{"value":"986075","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q674343$F3F2956A-B959-4000-817C-1AEA93F93333","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"834c45d526445b63ede129bf0252d3b47bed13e5","datavalue":{"value":"NP","type":"string"},"datatype":"string"},"type":"statement","id":"Q674343$8EDA74D8-9155-43A3-988A-FA8EDADE5637","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a428018fcb62c231dc4b5243845a1705be4384e3","datavalue":{"value":"polynomial-size circuits","type":"string"},"datatype":"string"},"type":"statement","id":"Q674343$A84D750E-19FE-4A90-9D25-68282C629125","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":"Q674343$7A81D100-0F6C-43FC-9436-0E2A0D51B9E7","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"0a147eab21c6312b6c1661bb524bde8b6cbce590","datavalue":{"value":{"entity-type":"item","numeric-id":1321029,"id":"Q1321029"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q674343$CE51BC85-6F81-45AA-88E9-2152740157CD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7b9c0297ccc7943530d7e60dae41b7cff33d7166","datavalue":{"value":{"entity-type":"item","numeric-id":1106840,"id":"Q1106840"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q674343$C44969D7-8954-4842-8713-F12235521A9B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fd4f9b219f54da4cc88e481211745b7b70548f30","datavalue":{"value":{"entity-type":"item","numeric-id":4039803,"id":"Q4039803"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q674343$90A5185A-F7F1-43BA-A92F-8DECEA417C3B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dd90f9daaeb4d762fab84117a161e37a40441abf","datavalue":{"value":{"entity-type":"item","numeric-id":4293543,"id":"Q4293543"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q674343$7166F472-569F-4DE4-9701-8C840A3CEC04","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f06e660485cbc895c0095c4f085a34cde29ca5c0","datavalue":{"value":{"entity-type":"item","numeric-id":3765250,"id":"Q3765250"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q674343$57A4E0CC-0359-4177-986A-55D6337DEAB0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2dfa7a166ec16661ae8b46b07e16851ca68a09eb","datavalue":{"value":{"entity-type":"item","numeric-id":3929039,"id":"Q3929039"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q674343$67C96C08-3CF0-4A20-82C0-12865143F882","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"df9b440a7e27b4753042460b886584e943bebd26","datavalue":{"value":{"entity-type":"item","numeric-id":3957950,"id":"Q3957950"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q674343$5520A413-F362-4727-B677-387C68045B5A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"aff365d8186cc4c7ca2a8c01bb1842652c3c232d","datavalue":{"value":{"entity-type":"item","numeric-id":4273947,"id":"Q4273947"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q674343$22218D87-E281-46E3-AEBF-53A28923971C","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":"Q674343$62CE42CE-14DF-4250-89C2-CF916B1B6AB9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"458ab467d1c5397109a383d0e5c939369d06a212","datavalue":{"value":{"entity-type":"item","numeric-id":3221403,"id":"Q3221403"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q674343$C3C3DDEA-8529-44AC-A77A-BF394BC77A4F","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"88ecdedeaf6afee30efcad8beda21e59fde3ae23","datavalue":{"value":{"entity-type":"item","numeric-id":4645178,"id":"Q4645178"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"aa715d05aebf7f0600affed7f8087091a7449416","datavalue":{"value":{"amount":"+0.7889644503593445","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":"Q674343$FA57D8A2-17EF-4FEB-8424-B6A3EBF0ED0F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e6db595d5ced97784a0281bb6ddc41990bec40b3","datavalue":{"value":{"entity-type":"item","numeric-id":2922647,"id":"Q2922647"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bed427957c8ce4c596a82ac5e0c817d79547329b","datavalue":{"value":{"amount":"+0.7862713932991028","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":"Q674343$8CFB933D-85F4-4D0A-841E-39FEF34D15B7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4617599a984945a3b99480b07e85e8ca75627ef3","datavalue":{"value":{"entity-type":"item","numeric-id":4910716,"id":"Q4910716"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"934ce1e02088a970682f3cae27d3a703e3463faf","datavalue":{"value":{"amount":"+0.7764870524406433","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":"Q674343$FD7A88F6-43D8-4542-B739-B4DF4E78DA96","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1c8dfa3243bee772ddf07ec8af346ba0e2dd5219","datavalue":{"value":{"entity-type":"item","numeric-id":3575158,"id":"Q3575158"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"963431b5eac5f60471561b0b24b8eba9e296b179","datavalue":{"value":{"amount":"+0.7763424515724182","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":"Q674343$D6006757-8527-4B30-97BF-D73741275589","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1339f261c7a40aa6d30a7831b30aeb7bb6f3bd45","datavalue":{"value":{"entity-type":"item","numeric-id":4210150,"id":"Q4210150"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cb1e2309b508489390b201a74bd9a951dbc3f029","datavalue":{"value":{"amount":"+0.7750022411346436","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":"Q674343$DC39D7EB-95C5-4453-8773-FFF72D1F3CD6","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"If NP has polynomial-size circuits, then MA=AM","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/If_NP_has_polynomial-size_circuits,_then_MA%3DAM"}}}}}