{"entities":{"Q1892937":{"pageid":1903679,"ns":120,"title":"Item:Q1892937","lastrevid":47328613,"modified":"2026-01-01T09:34:21Z","type":"item","id":"Q1892937","labels":{"en":{"language":"en","value":"Fixed-parameter tractability and completeness. IV: On completeness for W\\([\\) P\\(]\\) and PSPACE analogues"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 768743"}},"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":"Q1892937$110EE849-91DE-4838-ABC7-83BA9F6D17F0","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"5ad89b0053b873013b1035a3ad878807025cff7f","datavalue":{"value":{"text":"Fixed-parameter tractability and completeness. IV: On completeness for W\\([\\) P\\(]\\) and PSPACE analogues","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1892937$8C6D804C-9FBB-4A40-8272-6CE153AA349B","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"b9ee348a3d1bf4a8293f10b7dba4b3cbf21daaae","datavalue":{"value":"0828.68077","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1892937$0DA00D00-88A3-4779-BC59-EAD08EF29C1E","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"e75d733f779871214cef99f8b7c4c7bfaca4c1fb","datavalue":{"value":"10.1016/0168-0072(94)00034-Z","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1892937$B25F2E5C-B0DB-49A5-8EAA-76E24A8CD250","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"ab8e589e0f05b726ed805341754b58dfdd94f6f7","datavalue":{"value":{"entity-type":"item","numeric-id":1892936,"id":"Q1892936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1892937$01E06A7F-9B56-424D-A29D-92FABAA355E7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"057c48278a1d014d58f7703e66b1dc164eccfbc4","datavalue":{"value":{"entity-type":"item","numeric-id":175527,"id":"Q175527"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1892937$FE1311F4-6F50-4ACA-9C15-88874F81E1E4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"2356fe1f1f6d7960e11f0114cbd6aa7fe05024f7","datavalue":{"value":{"entity-type":"item","numeric-id":247180,"id":"Q247180"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1892937$E89E1FF9-CA57-45A5-9E53-E3CFC2BFC61E","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f91a4bcbc93435aed71775d25a4c5cd09e26f12d","datavalue":{"value":{"entity-type":"item","numeric-id":122505,"id":"Q122505"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1892937$72E38E99-2236-4821-88EA-A253E0FCF020","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"65b62b02172d5cc5f437b5dc9222cb8085a69445","datavalue":{"value":{"time":"+1995-07-26T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1892937$222094B4-3E20-4756-AA77-4C8200143E54","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"46853b6118c9c58903a86f8e2f3b6afff06b3f36","datavalue":{"value":"The paper devices some new results in parametrized complexity theory. In particular, it is proved that a number of concrete hardness results for W[P], the top level of the hardness hierarchy introduced by Downey and Fellows in a series of earlier papers.   This hierarchy for fixed-parameter problems is based on the logical depth needed to describe the respective problem in terms of circuits.   Furthermore, analogs of PSPACE are studied in the fixed-parameter setting. This is done via certain problems concerning \\(k\\)-move games.   Several aspects of the structural complexity of W[P] and related classes are studied. The class W[P] is characterized in terms of DTIME \\((2^{o(n)})\\) and NP.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1892937$55E9277F-CF07-4F61-83CE-1882BB9C6A98","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b4346faa01bb5fb0576370374d6456afd58d5666","datavalue":{"value":"68Q15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1892937$655220B3-D45C-4E06-9B61-ED982C6C2D4D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d7656d1c841701431b0b3d99d23720089a267cbb","datavalue":{"value":"03D15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1892937$CB242968-99A7-47AC-ACA4-E467FF406D7F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1892937$7FBE04E9-BC61-44AC-A360-2ABF5AD1154E","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"0d0b594e52495c98711b942690722eb52b6654e9","datavalue":{"value":"768743","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1892937$3596C6AD-DC83-4E3F-B886-35402F664EE4","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"10d78acbd24c774aa98397ac1aba46b0f66d3689","datavalue":{"value":"parametrized complexity theory","type":"string"},"datatype":"string"},"type":"statement","id":"Q1892937$C81DD821-9CA6-4F04-AF3C-A31AD31AA802","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"1d10661fc91809efd2235d25989d04b60ba8bbd5","datavalue":{"value":"Q56620260","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1892937$7B3B2C82-6603-4270-B05A-A61B5D37AF79","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":"Q1892937$D4DCEE56-1C84-4B7A-BDB1-72E4E2F10D0F","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"87f001f0cbad53dd7b0f7605c3f62967f6287c69","datavalue":{"value":{"entity-type":"item","numeric-id":4281539,"id":"Q4281539"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1892937$35A1621F-C525-41A9-91C2-54DA8C71DA78","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"63ff92b19145990fc8644b707e05527ac29992be","datavalue":{"value":{"entity-type":"item","numeric-id":4202212,"id":"Q4202212"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1892937$7D017273-9288-4AF6-AF8A-E4A5F4DAD171","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b261c10e21468e427874b1e0e6a2c99a79585d4a","datavalue":{"value":{"entity-type":"item","numeric-id":676315,"id":"Q676315"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1892937$20DFD571-2C88-4938-8CA2-CBB9130FFBF9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ff8610c6ac1bbc8943323b4984864ddb89c99d3c","datavalue":{"value":{"entity-type":"item","numeric-id":4764103,"id":"Q4764103"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1892937$65B7F2B3-ABFA-4544-9BA5-AA6968E8590A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d98f7bca7625c9749c75727f2dff082e7e78c44d","datavalue":{"value":{"entity-type":"item","numeric-id":4027320,"id":"Q4027320"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1892937$A2E050E7-F100-427F-948F-35764810FE79","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8fa1290987e9e9910315413923140808cd3d7e8a","datavalue":{"value":{"entity-type":"item","numeric-id":4852629,"id":"Q4852629"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1892937$73A4FD88-63ED-488B-8EBA-AAFD1D59C1A8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"500bfeba9231a071c9bfde5b167ca0a56cfc8d2f","datavalue":{"value":{"entity-type":"item","numeric-id":673779,"id":"Q673779"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1892937$9B95ED7A-A92C-4456-9D89-D3E007C84552","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7f72dbacf36642446a4b5f28604fada2a145433b","datavalue":{"value":{"entity-type":"item","numeric-id":4281497,"id":"Q4281497"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1892937$5F6F6213-6CE1-475A-BDFC-B4A8E4C7E258","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b6e20515d7fb50e98c7d3215121fe76d91ec6609","datavalue":{"value":{"entity-type":"item","numeric-id":4850549,"id":"Q4850549"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1892937$E9F3A96B-100F-437D-AF85-0114EB020A3E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e7b2a530a68bfaad2e30d4c748c3d5e58e744725","datavalue":{"value":{"entity-type":"item","numeric-id":4501141,"id":"Q4501141"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1892937$22523150-2DDF-4C14-BD4A-5DD0FB82209D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"46b6d70cfd3ba4ec276ffb558fe15410d7040457","datavalue":{"value":{"entity-type":"item","numeric-id":4127387,"id":"Q4127387"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1892937$A6C5DAF5-0FEE-4957-9AA6-7EFCC2FAA39A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"589a850c22d08c5e6e543ee69411f61b8b1fdb64","datavalue":{"value":{"entity-type":"item","numeric-id":2817636,"id":"Q2817636"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1892937$AF906033-5E89-4A0C-B964-985788794BB4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a39cd8982dfb6eed9035d1ac9860ec8a9d249a12","datavalue":{"value":{"entity-type":"item","numeric-id":4279511,"id":"Q4279511"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1892937$7D2208B1-939C-4737-8C3D-456DA02F21B8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f89a031afe32dfcbf4f8fba11966dba55c1408ae","datavalue":{"value":{"entity-type":"item","numeric-id":4179026,"id":"Q4179026"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1892937$05D084FF-2AE2-4B88-824A-688B42380BB1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"836ad2a04f82225da478ca9f694f5cd99360b315","datavalue":{"value":{"entity-type":"item","numeric-id":4198056,"id":"Q4198056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1892937$7720D492-C696-4462-9576-11C70C346ED0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"65049120db84eb3a64559cb6dce6f2ce61c91d9a","datavalue":{"value":{"entity-type":"item","numeric-id":3893305,"id":"Q3893305"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1892937$E1DB12B3-8054-47A0-812B-1E60C431F7B8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"176f92be0a5c8084cbea32a162c15c6e5a582bd9","datavalue":{"value":{"entity-type":"item","numeric-id":3936195,"id":"Q3936195"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1892937$024D30C0-CFE0-47C6-AA1E-62F0A45F1C26","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"398ef8bc27e00efd8312d46a33efaa0333728c17","datavalue":{"value":{"entity-type":"item","numeric-id":1892832,"id":"Q1892832"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1892937$48A8D0CA-1954-4090-B47E-DBF39127F228","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"248729ebc4d6876ccf402d4746249e334c3f8ead","datavalue":{"value":{"entity-type":"item","numeric-id":705888,"id":"Q705888"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1892937$9B486CD2-A753-463A-82D5-318563613326","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b773ee5b291ebab239e6e8e7787b49c4d2b3c4cd","datavalue":{"value":{"entity-type":"item","numeric-id":1248466,"id":"Q1248466"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1892937$161AF171-1B72-45FD-815D-E2B97FF66228","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"daa4261e427eaf02f6489e6ec72c6f49c24fb95e","datavalue":{"value":{"entity-type":"item","numeric-id":1127315,"id":"Q1127315"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1892937$381ED9CB-7E7B-473C-92E6-444D6E2921C6","rank":"normal"}],"P1635":[{"mainsnak":{"snaktype":"value","property":"P1635","hash":"c1d6b6d9a6117a1d30ca03d43bdde5610b87c3f9","datavalue":{"value":"journals/apal/AbrahamsonDF95","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1892937$8A920AE9-7F0D-401B-B589-96467CCA5756","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e4e2ee4ccc74158a459b96769f605834c34c9350","datavalue":{"value":{"entity-type":"item","numeric-id":4281539,"id":"Q4281539"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fcd64a1967f96d3b43996b39fc242157f129e2d9","datavalue":{"value":{"amount":"+0.8757725954055786","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":"Q1892937$DC8B7AFE-42CF-4875-A0BC-88039EB77494","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ba36a9df6fc141cc1345f3a11a53771d21776606","datavalue":{"value":{"entity-type":"item","numeric-id":673779,"id":"Q673779"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fcd64a1967f96d3b43996b39fc242157f129e2d9","datavalue":{"value":{"amount":"+0.8757725954055786","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":"Q1892937$BE44DD38-7261-419A-ADED-8EC6F414E99B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e86a5b7440186ac57df521dbb97d281323c32d63","datavalue":{"value":{"entity-type":"item","numeric-id":4281497,"id":"Q4281497"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"24789c3e2dae6483132b02670d9597c97efa2175","datavalue":{"value":{"amount":"+0.8382053971290588","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":"Q1892937$A58CBBE3-2EAE-40B6-9B75-3A02D1484372","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"354be04a5e3fdd59aab17426060ae6d5cbb43869","datavalue":{"value":{"entity-type":"item","numeric-id":557897,"id":"Q557897"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0871bdddb97ac0edd360fdfdf742ce95df9fc97f","datavalue":{"value":{"amount":"+0.8374725580215454","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":"Q1892937$EF8542F1-3C71-4BC3-8E0E-EFBDBFC71D0C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"46b346b4598bbd4175a3420c5fce008260265d43","datavalue":{"value":{"entity-type":"item","numeric-id":4852629,"id":"Q4852629"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"596372a2795539a5c6728ab29189932b1f59a5fb","datavalue":{"value":{"amount":"+0.8275803923606873","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":"Q1892937$3D0BD6BD-C997-4B7F-B476-522E8AC314B3","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1892937","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1892937"}}}}}