{"entities":{"Q1264143":{"pageid":1274893,"ns":120,"title":"Item:Q1264143","lastrevid":49338808,"modified":"2026-01-07T00:01:17Z","type":"item","id":"Q1264143","labels":{"en":{"language":"en","value":"Complexity of deciding Tarski algebra"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4128801"}},"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":"Q1264143$B550CA66-CCE6-43F7-960D-2FCB187FEBCA","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"7847843d6f2b5ad5bc2313b9dd812fbeac266b8b","datavalue":{"value":{"text":"Complexity of deciding Tarski algebra","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1264143$BDC48077-727A-4677-A4A3-38509421B7B3","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"4caa1362c049fd054d61843c705f07f462d80148","datavalue":{"value":"0689.03021","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1264143$958A8076-35C6-4EC6-967E-F7331CE8EAE7","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"c9320d861a81c0607fdfdcc27dd85dc6946dbbc6","datavalue":{"value":"10.1016/S0747-7171(88)80006-3","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1264143$FAD4FFE3-A2ED-43C6-93AE-6E74E68206A0","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"ea72303f92787da89554ee5fa15621068821a762","datavalue":{"value":{"entity-type":"item","numeric-id":99061,"id":"Q99061"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1264143$9CE4EE26-8F9C-485F-9283-9F339655265A","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":"Q1264143$65B99BBD-CF8F-4866-94C3-5D32C5E292A9","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"e375d5f70b6665df5067588263d3db0e228ecf55","datavalue":{"value":"Let (*) \\(\\exists x_{1,1}...\\exists x_{1,s_ 1}\\forall x_{2,1}...\\forall x_{2,s_ 2}...\\exists x_{a,1}...\\exists x_{a,s_ a}(P)\\) be a formula of Tarski algebra, where P is a quantifier-free formula with atomic subformulas \\((f_ i\\geq 0)\\), \\(f_ i\\in {\\mathbb{Z}}[X_{1,1},...,X_{a,s_ a}]\\), \\(n=s_ 1+...+s_ a\\), degrees \\(\\deg (f_ i)\\leq d\\), and the absolute value of each integer coefficient of \\(f_ i\\) is supposed to be less than \\(2^ M\\), \\(1\\leq i\\leq k\\). The main purpose of the present paper is to prove the following theorem: One can design a decision algorithm for Tarski algebra which determines the truth value of a formula of the kind (*) within a time polynomial in \\(M(kd)^{O(n)^{4a-2}}\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1264143$87DEB496-B317-4269-9DD7-31CB4498E7C8","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"59699d8ba436c4690eab2e3c0ee0a7ef0d967cec","datavalue":{"value":{"entity-type":"item","numeric-id":1177040,"id":"Q1177040"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1264143$ECE9FABF-89C9-46E7-BAB5-2281492BA66F","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"d7656d1c841701431b0b3d99d23720089a267cbb","datavalue":{"value":"03D15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1264143$8BE2A7A5-4A67-431D-B37E-05D309C36260","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"407654cf92f0702e03297e7fe541e25fa3f13c2d","datavalue":{"value":"03B25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1264143$5ADA318F-7C18-43F7-973D-0EAFA8A3EEF0","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"2a8b66be4e2ced3744e8c0835252afc67abdb023","datavalue":{"value":"4128801","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1264143$49CEEDB8-153A-4D2A-9DD9-D7E2148B0217","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a862f016acc1e519aa7b6644887bfca464692961","datavalue":{"value":"polynomial time","type":"string"},"datatype":"string"},"type":"statement","id":"Q1264143$29865886-DE32-47DE-9A6D-4251458B6B55","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"902b4b5ba745d03cb4915bdd54611c2b7c9a6465","datavalue":{"value":"Tarski algebra","type":"string"},"datatype":"string"},"type":"statement","id":"Q1264143$30EFA1D4-C409-40D5-B2A1-20CDF4E5C121","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f3018f13ec4565557bf025633f394ef25a05fe3b","datavalue":{"value":"decision algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1264143$D66CCF3D-E1E8-4F2F-BFC2-8AC1091404AE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3d085daaa64e97690f20fe940dba3ce1b91aec36","datavalue":{"value":"truth value of a formula","type":"string"},"datatype":"string"},"type":"statement","id":"Q1264143$D63FCC01-A529-40AE-8CED-ECDB73879A6B","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"a4a79399764b502030de9c1fe7fb099f6c796d65","datavalue":{"value":{"entity-type":"item","numeric-id":1583885,"id":"Q1583885"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1264143$348FC156-B38D-4367-8979-3F6C608292CF","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":"Q1264143$8A8DEF64-D181-4986-B035-CA43AF76EF17","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"c21355d631011ed037f0c70ab644c2ea5c134703","datavalue":{"value":{"entity-type":"item","numeric-id":4747509,"id":"Q4747509"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1264143$E9B41AFC-12D6-4F73-B8BA-81A7B37A2806","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7fa745fed236513fb52d9febacf8c197e209a16c","datavalue":{"value":{"entity-type":"item","numeric-id":3728104,"id":"Q3728104"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1264143$0846153A-C47A-46B1-A406-8F761B7A4741","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5bc0d7c2f9fbebdd682ae380725d8093d2d4a292","datavalue":{"value":{"entity-type":"item","numeric-id":5187264,"id":"Q5187264"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1264143$0A8D1E15-1DE4-4CD0-8BA0-5828FEFEFF39","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3f1139f87ae775ef65a114512a6abaadba3bdc67","datavalue":{"value":{"entity-type":"item","numeric-id":5184990,"id":"Q5184990"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1264143$B21CE6FE-BBE0-446B-ACC1-061EC61BC84D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8f215b4be5d109fd9d816f69f638d95cc094372e","datavalue":{"value":{"entity-type":"item","numeric-id":5552751,"id":"Q5552751"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1264143$0A9A7818-D4F9-4B12-8E10-EC2EA5F60CA6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c4d7798eba50e0ffe1e4306d4a4aa338f6be7be4","datavalue":{"value":{"entity-type":"item","numeric-id":4079605,"id":"Q4079605"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1264143$AD67DEFA-5404-43AF-A65C-BAB1540C6CD2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cca8ae3740fcfb5a7e9f346758fcdd72ac5497a7","datavalue":{"value":{"entity-type":"item","numeric-id":4082296,"id":"Q4082296"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1264143$27DF9E88-966D-4B72-8059-31C4D286064B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c451625003fa8ec403d3e1a215907cec62a72c9c","datavalue":{"value":{"entity-type":"item","numeric-id":5184991,"id":"Q5184991"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1264143$96AF325C-1CE8-4D4D-B2A7-6BB7352FB861","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"846b1160ca243928ccbec992bdc372e4238babd3","datavalue":{"value":{"entity-type":"item","numeric-id":3882558,"id":"Q3882558"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1264143$8F210112-56C2-4489-B9A1-F1695B133902","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f7a32ed3ebe2a6943b21f5610ce09de81d64f5fd","datavalue":{"value":{"entity-type":"item","numeric-id":3820004,"id":"Q3820004"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1264143$FDF5D419-5E92-4321-AB45-B76BC69E57DB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d7d21ba7c9e01a1e4d50952aba9cb27df7aae8db","datavalue":{"value":{"entity-type":"item","numeric-id":1113939,"id":"Q1113939"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1264143$3C3CC400-FACB-4F9C-AD99-BE6641A92E2B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"94af4b398439d78f99f728572ea461069cbeaa2e","datavalue":{"value":{"entity-type":"item","numeric-id":5633582,"id":"Q5633582"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1264143$1EBD0178-E0E2-4F5D-8B06-E4E904D92504","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3a5406ea7669ed616e0ac659900417e7fcb90273","datavalue":{"value":{"entity-type":"item","numeric-id":798314,"id":"Q798314"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1264143$A63C499E-74AF-4EED-969B-8B38E7750618","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f6899b40a48bb6dd55553fc9b55d2ab3a1166c63","datavalue":{"value":{"entity-type":"item","numeric-id":5588717,"id":"Q5588717"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1264143$6B17E8AD-BA39-41F4-86ED-A802A56AB753","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ed7003180117687f05347c72721ff273c213c8a3","datavalue":{"value":{"entity-type":"item","numeric-id":1152212,"id":"Q1152212"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1264143$941CA7B7-489E-477D-8BA2-2E0951C0B514","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1eb5d7dec27c8818f722e687ece5f845ee917c3f","datavalue":{"value":{"entity-type":"item","numeric-id":3684200,"id":"Q3684200"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1264143$7017963A-6750-404B-BECA-8554336019E4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dbc8272a2eed684dcc743719a6651c947badf1e2","datavalue":{"value":{"entity-type":"item","numeric-id":1836661,"id":"Q1836661"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1264143$0C8971D0-2044-479C-964E-25E05C0C1FA5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5b515ced739c6c8e682cf74e7321d82d15295643","datavalue":{"value":{"entity-type":"item","numeric-id":5736681,"id":"Q5736681"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1264143$278548A0-14CD-4CA8-86C7-C94CBA36376D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"813f00e49fcb12172c27504dfeecb9018f840f1f","datavalue":{"value":{"entity-type":"item","numeric-id":2651859,"id":"Q2651859"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1264143$9918CB45-94BE-45D7-A8FA-80879BED012D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"82d5ab76b12c558c2b19763ca1807402cbe3af0c","datavalue":{"value":{"entity-type":"item","numeric-id":4771357,"id":"Q4771357"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1264143$F0BB8842-22A9-480C-A303-10E4432A5C3C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c8be9375a315209f41df1b38374a5e7e956d28bf","datavalue":{"value":{"entity-type":"item","numeric-id":5807665,"id":"Q5807665"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1264143$FE59DC33-F8AC-41C1-A4AF-7A38930CC8FF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a4b12d8b6db4861de194e04359d968f46f56d4ca","datavalue":{"value":{"entity-type":"item","numeric-id":3746798,"id":"Q3746798"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1264143$FA4620D4-AF3A-43BC-BA5C-881FF8C11693","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e92de3f05590685578d3ffc2c8aee29bbdd76883","datavalue":{"value":{"entity-type":"item","numeric-id":4137157,"id":"Q4137157"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1264143$E277B6CC-95E5-4EF2-8D8C-8BE6E432B908","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"7de2c0342a14862aaeb53f61b025cf6316de1bb4","datavalue":{"value":"https://doi.org/10.1016/s0747-7171(88)80006-3","type":"string"},"datatype":"url"},"type":"statement","id":"Q1264143$2FE51CDE-6AA9-49AB-8438-68695C9E3C54","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"1df07755cda3931bc5d2bd5a7f934fc65b6a2511","datavalue":{"value":"W2102074804","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1264143$F2ADCB1E-47E8-40F7-A5F9-9F15C13B2A73","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9b740e4ae19100c56f40c040b1099272f9c8a9e0","datavalue":{"value":{"entity-type":"item","numeric-id":3483265,"id":"Q3483265"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"38cd47c126a2bad700ac819082e114de635a4d03","datavalue":{"value":{"amount":"+0.8015971183776855","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":"Q1264143$C5B6EB5B-6ABF-4A0B-BCE0-5A588D43F735","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1ed35c47223a16298842485a66014826d905e4a1","datavalue":{"value":{"entity-type":"item","numeric-id":5187264,"id":"Q5187264"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2634f8dec53dd34fcee118d6f067e4df5b48eaf0","datavalue":{"value":{"amount":"+0.7788530588150024","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":"Q1264143$A04B527D-C9B6-458E-B209-0549E9057463","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8610d660f16a92d1153e7a3d9ccfb80ca2679f08","datavalue":{"value":{"entity-type":"item","numeric-id":4713865,"id":"Q4713865"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"360d300a5ccc7b1b8402170843df7eb7661cd6a0","datavalue":{"value":{"amount":"+0.7720696926116943","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":"Q1264143$0C0FE874-878A-460B-BD67-902451E90A86","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a5cae51ea13ed26b6860e3b2744a40e9c4f8b73f","datavalue":{"value":{"entity-type":"item","numeric-id":3480175,"id":"Q3480175"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f796baed92b1cec0e44cf17f301f538304eaec2d","datavalue":{"value":{"amount":"+0.7657285332679749","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":"Q1264143$37748C2F-11AE-4E91-AFAB-743320352258","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0e703b606f36427127e5a5f6edee03487eab9391","datavalue":{"value":{"entity-type":"item","numeric-id":1185457,"id":"Q1185457"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2f321cef90d4eddec5e7da28a0ad2e46bff199e7","datavalue":{"value":{"amount":"+0.7534312009811401","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":"Q1264143$81833D6A-9CEF-4918-AAF0-71AE835A5873","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1264143","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1264143"}}}}}