{"entities":{"Q2453562":{"pageid":2464305,"ns":120,"title":"Item:Q2453562","lastrevid":52012487,"modified":"2026-01-20T18:20:58Z","type":"item","id":"Q2453562","labels":{"en":{"language":"en","value":"Bounded-width QBF is PSPACE-complete"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6302137"}},"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":"Q2453562$5A2DCA53-2E1F-4B3A-B6DA-E8C672346D54","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"ad7a41c47d08cd3a93b3d3f2925e5c9cccf476bd","datavalue":{"value":{"text":"Bounded-width QBF is PSPACE-complete","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2453562$6C714318-83CE-45DF-90BC-7C9E3222ACBE","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"4a36046c6bab10beb67d3dac059bb6dec774c705","datavalue":{"value":"1311.68072","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2453562$13C42FC4-8DAA-4F3A-B2D3-5D8D3EA2CE77","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"691b2efa6b7a6124eda9dac7addda22440a9eb76","datavalue":{"value":{"entity-type":"item","numeric-id":458459,"id":"Q458459"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2453562$C0BB3340-BD3D-4791-97AB-9EB4E7E65B90","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"f0e0f3e0e584192bb6b94e67d7eb7d48b0f94b4e","datavalue":{"value":{"entity-type":"item","numeric-id":2453561,"id":"Q2453561"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2453562$6BE6ED39-8B6E-4493-B9DA-09AC9740839D","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"3340243f57e05f2265c56423c388055a14b114fa","datavalue":{"value":{"entity-type":"item","numeric-id":107189,"id":"Q107189"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2453562$270B142A-B3F3-40DF-B614-9135338D07D4","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"7deb189b65cc3fc27b859d71d92363347a0068f0","datavalue":{"value":{"time":"+2014-06-10T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2453562$2F9ACDF5-9DB0-486E-8234-E6ACD8E79341","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2453562$4DF4710B-EF40-480B-B036-4C77489D2012","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"9a994e1774be82d1378eb4215aaecd128c01dabb","datavalue":{"value":"6302137","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2453562$3E2B3AAB-A17A-461A-B87B-E4CF5A49A97B","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b81b0e661ffd7a2b0cf4d74a6388abe874250e20","datavalue":{"value":"tree-width","type":"string"},"datatype":"string"},"type":"statement","id":"Q2453562$DD04B77C-9CFC-474B-96E6-89CACBD796E1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0d18b5d882b6d2f6b783adad4985d68c838d00e6","datavalue":{"value":"path-width","type":"string"},"datatype":"string"},"type":"statement","id":"Q2453562$F02216C2-E574-4AC1-9444-74FE6D0DD8B3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9f805b7faea11905894680953dd9b9dfc3dd4258","datavalue":{"value":"quantified Boolean formulas","type":"string"},"datatype":"string"},"type":"statement","id":"Q2453562$DDE29F76-A0BF-45E6-882A-2AD9345B6C9C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a05cfd9da536bc8387292ab9359d3f7e9902a360","datavalue":{"value":"PSPACE-complete","type":"string"},"datatype":"string"},"type":"statement","id":"Q2453562$36D06602-6703-4B83-98B8-E2CC0D6F779B","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":"Q2453562$7DC98351-F9AA-4AE1-8510-1B885CB4B8F3","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"cd2bb8505c2154416b0a0ea1cca0e35f51adc635","datavalue":{"value":"https://doi.org/10.1016/j.jcss.2014.04.014","type":"string"},"datatype":"url"},"type":"statement","id":"Q2453562$B760EFB9-DE8C-464C-8248-1893ED71396A","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"601dab14a2523ea78416223da5ecde2864385266","datavalue":{"value":"W2007381442","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2453562$E640243B-F7FC-480A-B5D3-D19A42A0BB21","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"cc5bdfe9e8ce1cefa466590964d38f16789200ff","datavalue":{"value":{"entity-type":"item","numeric-id":1116363,"id":"Q1116363"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2453562$4F0BE47F-0B34-4B84-BB55-030D95434AD4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8b82a19190ac54ccd87a58918a70a29fe1833a9e","datavalue":{"value":{"entity-type":"item","numeric-id":4090322,"id":"Q4090322"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2453562$60B87599-902C-4CE4-90E1-34B9670E4CC6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e48e4c3d4f67d5a6188c0cae2c82d726b6173fb2","datavalue":{"value":{"entity-type":"item","numeric-id":2986797,"id":"Q2986797"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2453562$702CB26A-211D-4670-B277-E2B9E6DFB9E6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"72df03d77e1bc06662d09c4718408a862df26da2","datavalue":{"value":{"entity-type":"item","numeric-id":1891159,"id":"Q1891159"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2453562$37D3C1A4-CA5F-4320-82D7-5246B5C2E18A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ad5843107a675ef426cb1b75becf5e9aa46b5362","datavalue":{"value":{"entity-type":"item","numeric-id":5900311,"id":"Q5900311"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2453562$A4721455-15BF-42E7-9F59-7A5F4F967EC4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"afc61a2037feef2b958c658698dd68bdb6481612","datavalue":{"value":{"entity-type":"item","numeric-id":1102137,"id":"Q1102137"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2453562$2A4E237D-21F5-43D3-88B5-C3AF1814D521","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1cf035d2fecb7e445991dd16e141f37bab3768a8","datavalue":{"value":{"entity-type":"item","numeric-id":1254112,"id":"Q1254112"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2453562$EF0A1F97-8DC8-4571-9DAB-DABF89617350","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"67f90dc47ee396b12cae5fa6d2394d18487359cb","datavalue":{"value":{"entity-type":"item","numeric-id":5394580,"id":"Q5394580"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2453562$9EA28F19-3C15-4AA2-8A99-10CD7D161A26","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"770bb68de47752f527df3eb5fd0239815f0bd638","datavalue":{"value":{"entity-type":"item","numeric-id":3751595,"id":"Q3751595"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2453562$CBD9E93C-47FF-4D79-B275-1BEEB8EACE56","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"41ab95cfd69e10430c9e72fb53fae7f5a4250a3f","datavalue":{"value":{"entity-type":"item","numeric-id":4947393,"id":"Q4947393"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2453562$9A19844E-4E10-4E6F-9B6A-4095A06FAB68","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"e40f423802d63af87639bf335d84de586d38c967","datavalue":{"value":"10.1016/J.JCSS.2014.04.014","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2453562$B2097887-CD20-4F22-AFD3-28AC9B280084","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"874ad15df0aa3478d70d76d4f0ec60725ced2a9f","datavalue":{"value":{"entity-type":"item","numeric-id":2957870,"id":"Q2957870"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"acf586c8e92e68b63e0eff36d92611fd4bb247c6","datavalue":{"value":{"amount":"+0.9531665444374084","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":"Q2453562$C6788184-80E3-4355-A6A6-23C1C80FC250","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8f75d58a9fba9ceef778618030eccb0ed9b1e160","datavalue":{"value":{"entity-type":"item","numeric-id":4608723,"id":"Q4608723"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0f11f24cdd387e3ae66cc6da9adbff93bc077c61","datavalue":{"value":{"amount":"+0.7901948690414429","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":"Q2453562$3EF04229-FC76-48E2-BAE5-3B58374D90CB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c211ed7df0db7f53cfc52d73db3f5f66deb9a8f0","datavalue":{"value":{"entity-type":"item","numeric-id":4601867,"id":"Q4601867"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4dbca5c5c26f88c1e421ac458fea83909d56cbef","datavalue":{"value":{"amount":"+0.7879040241241455","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":"Q2453562$97F1B8BB-E1C6-4830-B1D7-CC40C22C7A49","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f11e6883acb5a4ee0dc518461c6a12ab8c520e0d","datavalue":{"value":{"entity-type":"item","numeric-id":2304627,"id":"Q2304627"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"aa4ecf24d6e7b3ab63988ae5595dacdff65b2eee","datavalue":{"value":{"amount":"+0.7826594710350037","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":"Q2453562$A28C2F1E-1AB7-48BE-B9C6-2E30E06C0299","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4be27cb011c2b316d969f24d656bed1628df0864","datavalue":{"value":{"entity-type":"item","numeric-id":5145632,"id":"Q5145632"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"db9d53723a73c75b1d83551230c57c8556f850c6","datavalue":{"value":{"amount":"+0.7732507586479187","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":"Q2453562$1DC28000-FD54-40B9-929A-CE19A8F87424","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2453562","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2453562"}}}}}