{"entities":{"Q685437":{"pageid":687286,"ns":120,"title":"Item:Q685437","lastrevid":47188978,"modified":"2025-12-31T23:10:56Z","type":"item","id":"Q685437","labels":{"en":{"language":"en","value":"Interactive proof systems and alternating time-space complexity"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 417367"}},"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":"Q685437$E6833597-A099-498E-B56F-00368335F234","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"52191c4d584e4619886629f92a4f181c3a8c4e38","datavalue":{"value":{"text":"Interactive proof systems and alternating time-space complexity","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q685437$BD97BBD8-DC86-4293-B868-65CF4DAF7F29","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"4487c1bf214cb8b91cecb9493595ea1319a67deb","datavalue":{"value":"0777.68039","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685437$79E95629-5D00-4FF0-B6E4-430B0AE9BFFB","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"a16f44310227d1fecc3fc93acdefe8ef33050c29","datavalue":{"value":"10.1016/0304-3975(93)90210-K","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685437$E1A5E80E-24F2-4E11-AB30-09AEFDD6C195","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":"Q685437$AA7E63B9-BC87-4D64-B89A-A1B64BB1E08D","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"0e0802548d3bb1db3e5fc95d663413182f61537a","datavalue":{"value":{"time":"+1993-12-15T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q685437$C3261801-87BC-44FA-A924-D82A35184D72","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"b15573937b39c31585591c96cd5bde559cfab14a","datavalue":{"value":"We show a rough equivalence between alternating time-space complexity and a public-coin interactive proof system with the verifier having a polynomial-related time-space complexity. Special cases include the following:   \\(*\\) All of NC has interactive proofs, with a log-space polynomial-time public-coin verifier vastly improving the best previous lower bound of LOGCFL for this model \\textit{L. Fortnow} and \\textit{M. Sipser} [Interactive proof systems with a log space verifier, manuscript (1988)]; later version appeared in \\textit{L. Fortnow} [Complexity-theoretic aspects of interactive proof systems, Ph. D. Thesis, Laboratory for Computer Science, Massachusetts Institute of Technology (1989)].   \\(*\\) All languages in \\(P\\) have interactive proofs with a polynomial-time public-coin verifier using \\(O(\\log^ 2n)\\) space.   \\(*\\) All exponential-time languages have interactive proof systems with public-coin polynomial-space exponential-time verifiers.   To achieve better bounds, we show how to reduce a \\(k\\)-tape alternating Turing machine to a 1-tape alternating Turing machine with only a constant factor increase in time and space.","type":"string"},"datatype":"string"},"type":"statement","id":"Q685437$42B4FABC-A112-4D3C-9856-A7107D8615A7","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b4346faa01bb5fb0576370374d6456afd58d5666","datavalue":{"value":"68Q15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685437$51BA9071-BB03-4F2B-A9BF-78FF27296093","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a7dde57cbaf704d564d8f981ca98d6340e3d4aaf","datavalue":{"value":"68Q05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685437$C60F825B-3C12-41A1-8E0C-2BDC27833E2E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"35bbdcbda53152c249a7f99650e19b5ef62999f2","datavalue":{"value":"68Q10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685437$24861729-2BF2-4F2E-B18A-C0D37E85F03E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685437$E417B7F0-88A5-4DFC-A3AF-41BA448E3B5A","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"ca3423365e2be702b686162be1140bd76439f2f2","datavalue":{"value":"417367","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685437$CCD3C5C2-62B0-4EAD-A2B5-D4E1D176044B","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d9199d2a34e605cbe9885e79eb427d00c0efb1ae","datavalue":{"value":"nondeterministic computation","type":"string"},"datatype":"string"},"type":"statement","id":"Q685437$AE4D56E6-7249-4CBC-91D4-3C3822BBBC83","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4dd2ac5bf791cca7a9ea444bd64a1c01f4a935f4","datavalue":{"value":"alternating time-space complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q685437$6A0B4D0A-8D54-4E27-B971-70B7A28BF4DD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"97e49dc09424a902c36096ed73c08b46183cb547","datavalue":{"value":"public- coin interactive proof system","type":"string"},"datatype":"string"},"type":"statement","id":"Q685437$68A0B1C3-7D4F-44D2-8CBC-7A72FC160E47","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6c22bf29c4e2c24e3aaa6371a05fbbc7a8210986","datavalue":{"value":"log-space polynomial-time public-coin verifier","type":"string"},"datatype":"string"},"type":"statement","id":"Q685437$7F798B90-581D-4EEF-AC92-ABC5D550A7CB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"606d7691d630d8ce11342fa6dc826a2e76a2f488","datavalue":{"value":"polynomial-time public-coin verifier","type":"string"},"datatype":"string"},"type":"statement","id":"Q685437$32D43150-E957-481F-A50D-9EBC0962E861","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d1145dc1c9086d33ddd9985f505026b90d304cf1","datavalue":{"value":"public-coin polynomial- space exponential-time verifiers","type":"string"},"datatype":"string"},"type":"statement","id":"Q685437$32573D3E-351C-4B13-BCFA-445BE2F187FD","rank":"normal"}],"P16":[{"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":"Q685437$6C30896E-C204-42D3-8789-2335EA853D83","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"fc7d1a4eaf68ad28c765a87d96a0e4f61af86791","datavalue":{"value":{"entity-type":"item","numeric-id":2453542,"id":"Q2453542"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685437$9CB04D27-4EC9-429C-BAF9-136D7734801B","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":"Q685437$4B30EA21-774F-44AE-BC6C-7557D40735F8","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"233b0d1b99b8001d6aea8c4b2bab778ddad6115e","datavalue":{"value":{"entity-type":"item","numeric-id":685721,"id":"Q685721"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685437$256EBE9E-021F-4175-9E90-6C30E6A9C0E5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"98d1f99209118318c5224afcbafe9d76aa7f8425","datavalue":{"value":{"entity-type":"item","numeric-id":1155607,"id":"Q1155607"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685437$A2C4EA21-7032-450B-804E-4ABDF524A506","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":"Q685437$FE383F04-921F-42B7-8744-3650D0737869","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"212cb9e82a13f5fba59b074b1d5d360f9e3452c7","datavalue":{"value":{"entity-type":"item","numeric-id":1118406,"id":"Q1118406"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685437$E8C983F4-1751-4553-93DD-19FA9F08B2F8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ae477ba2300400eec2908d55329cb4248dc074d4","datavalue":{"value":{"entity-type":"item","numeric-id":3833627,"id":"Q3833627"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685437$95BC31D9-7F60-4837-8E77-D6A74699B1E7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2043397a54eaa38033021fac24881dafefacec7d","datavalue":{"value":{"entity-type":"item","numeric-id":5592246,"id":"Q5592246"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685437$B93C98FC-C7ED-4B0C-8BA0-1C62694537FA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b7dfd09693191dadd4557c3575407afe38818cf1","datavalue":{"value":{"entity-type":"item","numeric-id":5658032,"id":"Q5658032"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685437$DE50A26A-EC03-4A90-BE4C-1906B5CF1B9C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"37ddc25bc6ddeb4fef28927db93d392a886040f2","datavalue":{"value":{"entity-type":"item","numeric-id":4302792,"id":"Q4302792"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685437$BDD360CB-AEB2-4390-8155-55CEB6D0E372","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5a589b2b8385ccd4be46b5ea02a14f7621bb80bc","datavalue":{"value":{"entity-type":"item","numeric-id":1141480,"id":"Q1141480"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685437$DD5AB776-4567-4763-938C-9FCC8C18D52B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9920c3ac00d626f59f95283223bd4fb6ae680345","datavalue":{"value":{"entity-type":"item","numeric-id":1152951,"id":"Q1152951"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685437$D033C2AB-C66E-4F1D-8D33-DB484C7868B5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5d268b2809bbcd70c788c93a5e38330e04b05334","datavalue":{"value":{"entity-type":"item","numeric-id":4302793,"id":"Q4302793"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685437$5286FDB7-7FA5-4A82-9F28-20148C81ACB1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ffd62d053722cf5d751600fb75eb7547849856ad","datavalue":{"value":{"entity-type":"item","numeric-id":4149509,"id":"Q4149509"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685437$28A5D5CE-09E8-42FF-AC1F-F3DDD222C76D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a0e11de7132c10164732e9b26841e64c659613e5","datavalue":{"value":{"entity-type":"item","numeric-id":4142695,"id":"Q4142695"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685437$9E49DFE5-9FA5-49E1-A116-296EF89CBC9E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"59a71ee27fc06ad3b0b4b92d7dad58a5649789e7","datavalue":{"value":{"entity-type":"item","numeric-id":4158497,"id":"Q4158497"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685437$45FB0B21-DF16-403A-8A01-04633B2F8F1E","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9ee44f05f8e31fa27cc2967d2c9aa99474f8fa49","datavalue":{"value":{"entity-type":"item","numeric-id":4035675,"id":"Q4035675"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0c6fab009ab768203741e7ba09f53bc7259b9b91","datavalue":{"value":{"amount":"+0.9860228896141052","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":"Q685437$49A18876-A986-4B2C-8AC1-7FD2315F48D2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0d3e339fbf347749fb383ab4d8935758906d319f","datavalue":{"value":{"entity-type":"item","numeric-id":293359,"id":"Q293359"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ba154a9a1fee7aec4c0140aea199cbc67fd727a8","datavalue":{"value":{"amount":"+0.9853904843330384","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":"Q685437$D83F8A6B-FC00-41E2-8C61-DE960B859B33","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ab722b0061c3556457fbc46f085c90f763d396a3","datavalue":{"value":{"entity-type":"item","numeric-id":6487945,"id":"Q6487945"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"357ebd930cc8b98020846dbe8809bc83e6b2f1c6","datavalue":{"value":{"amount":"+0.82607102394104","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":"Q685437$FD150870-5CD8-4B4F-8756-C63E0D7D756C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"11b47b1bc9a30f047026c46522ccacfe18815d2d","datavalue":{"value":{"entity-type":"item","numeric-id":5047165,"id":"Q5047165"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0b8a5f59e25e130f5f9e1bc62fdd1394d788c1c2","datavalue":{"value":{"amount":"+0.8211463689804077","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":"Q685437$9881D752-15CB-41D0-B361-F69F68FAC5D7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"84f13aee1b1b9049f646536e2fe35347157cb09d","datavalue":{"value":{"entity-type":"item","numeric-id":4281691,"id":"Q4281691"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"00d0bc3f94903f9e3917eeb44e64f8964abab2a5","datavalue":{"value":{"amount":"+0.8203086853027344","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":"Q685437$F944E2C3-3657-48B0-A521-018D990FBFEA","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:685437","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:685437"}}}}}