{"entities":{"Q1853067":{"pageid":1863809,"ns":120,"title":"Item:Q1853067","lastrevid":73896951,"modified":"2026-04-14T17:39:33Z","type":"item","id":"Q1853067","labels":{"en":{"language":"en","value":"On the complexity of one-shot translational separability."}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1856408"}},"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":"Q1853067$F4C39A6F-ADC2-41E8-8B2B-85A3B36F6B55","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"5c76d8943fff301907bbfbb5e8494238b6d8470d","datavalue":{"value":{"text":"On the complexity of one-shot translational separability.","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1853067$481EFFB9-1F68-41BA-9FD7-0F0465AA886D","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"3ed372a56ff531b9bf4de42a48572d6804e68c14","datavalue":{"value":"1043.68065","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1853067$929FB078-AB23-4E5C-B126-ED16CC6DF453","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"262eb5f875d3d0c881049d7fd1e1a1f3d11ebb6c","datavalue":{"value":"10.1016/S0020-0190(01)00333-7","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1853067$0C25F87F-189E-48E0-A134-86989DDD23F5","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"774402e509d2d2c6094edda8105d9433510930b1","datavalue":{"value":{"entity-type":"item","numeric-id":1274557,"id":"Q1274557"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853067$D76478E2-868A-49FB-8463-DA66C88290D5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"35b873b12e1f38b9b54ebe15e592fd54e5dec7f2","datavalue":{"value":{"entity-type":"item","numeric-id":1183394,"id":"Q1183394"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853067$9ADBC4C3-5182-4693-AB1D-4CB5A9F6FDF9","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"52fa7d44b58d0511cb8993765bd916aef86052d8","datavalue":{"value":{"entity-type":"item","numeric-id":63092,"id":"Q63092"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853067$48EE915C-BF8C-44C6-85A1-EFE35B0C999F","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5b5e42af6f5e314fbfeffbcec47ae99c9eed44fd","datavalue":{"value":{"time":"+2003-01-21T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1853067$B6109132-357B-4065-B4F5-B4B2221604EA","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"8814c36554b3c735f6419a31914995b0dce9bcb2","datavalue":{"value":"The problem of deciding whether 2- or 3-dimensional objects can be separated by a sequence of arbitrary translational motions is known to have exponential lower bounds. However, under certain restrictions on the type of motions, polynomial time bounds have been shown. An example is finding a subset of the parts that is removable by a single translation. In this case, the main restriction is that all selected parts are required to be removed in the same direction and with the same velocity. It was an open question whether the polynomial time bound can be achieved if more than a single velocity is allowed for the moving parts. In this paper, we answer this question by proving that such `multi-handed' separability problems are NP-hard.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1853067$31599D80-39FD-43DC-82DD-294009406EEC","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1853067$2748560B-13D5-4D3F-A083-FF1EAC32A0AB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"159426a5937e62cfbbcc198dd4848ab52d6e715e","datavalue":{"value":"68U05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1853067$14EB0BF0-962A-4FEE-8E3A-0866087DE2DF","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"9ab5807ce7ecee84a855887d6179d17e58e703f7","datavalue":{"value":"1856408","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1853067$E901E201-E7F4-4F6F-AB8E-383F5824A734","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"da67da54e89e7c80f20f3f95c3ceec18bb927753","datavalue":{"value":"Computational complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1853067$71006CE6-33C9-4A16-83DD-53D4A465DAF5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0e0032d5eb6e50d1531a77194b8aacf827853e28","datavalue":{"value":"Computational geometry","type":"string"},"datatype":"string"},"type":"statement","id":"Q1853067$53602214-56FE-45AA-9E79-0A1AD61DE614","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fe65b3261bff3de7b6f44224c3c4e06c053b39da","datavalue":{"value":"Assembly planning","type":"string"},"datatype":"string"},"type":"statement","id":"Q1853067$F0153FEA-2B02-4D10-BF0A-BFD39A5B2449","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3c328139a68602b243aff2a7a63bdc5330f4dffa","datavalue":{"value":"Motion planning","type":"string"},"datatype":"string"},"type":"statement","id":"Q1853067$D4B0FFA5-C617-4372-B205-49F020A0D29D","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":"Q1853067$BD272333-D9FA-4B18-B6D0-1D13429A6272","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"6883be78cd007edc610c20335503597d083bd5a6","datavalue":{"value":{"entity-type":"item","numeric-id":4875176,"id":"Q4875176"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853067$B7A3524A-5DEB-41DB-B4AB-BAF48C89D76D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"04a9e3f000fa8d933c0a5838a7db9774de221abe","datavalue":{"value":{"entity-type":"item","numeric-id":3326357,"id":"Q3326357"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853067$680311F1-C22D-4ADF-ADE2-8E48508B2A32","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"25b026e498c7466f890693e678f90760ff4b1c4e","datavalue":{"value":{"entity-type":"item","numeric-id":3772828,"id":"Q3772828"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853067$018EE7EF-D8BD-4699-8CDB-AD837736904F","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":"Q1853067$C7AA4731-4DB8-4894-9A65-2F612455EB7E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"daff5e0986d4d3e9ad52d2bcdb42900c788e0e06","datavalue":{"value":{"entity-type":"item","numeric-id":1313730,"id":"Q1313730"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853067$99660419-EF20-4661-AFFA-F4CD2FB97B8B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3916850d6a3e25880a1beea606cccf13889f177a","datavalue":{"value":{"entity-type":"item","numeric-id":672026,"id":"Q672026"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853067$3D4A0AC1-F951-4609-B883-05FBD806F8AD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8dcaa483cc5fd62ca56d2b9fc1e4c471aa718a22","datavalue":{"value":{"entity-type":"item","numeric-id":1274558,"id":"Q1274558"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853067$0459C8D9-75EF-4A39-A47C-EED110629A0B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"44c8aa352bca58eb4adbb088306a50560332279f","datavalue":{"value":{"entity-type":"item","numeric-id":1892580,"id":"Q1892580"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853067$20D1ADD0-38ED-479E-B524-5FE42A342883","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"553ee6d34e85d91f556a2f3e37fded53f6f5eb2f","datavalue":{"value":{"entity-type":"item","numeric-id":1338963,"id":"Q1338963"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853067$BAF17197-5A45-4056-B3E4-75135977AE68","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"179e0a9d46a8b7483726a7a65581cc4b382ad7bf","datavalue":{"value":{"entity-type":"item","numeric-id":3716330,"id":"Q3716330"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853067$D2F5C502-2DF2-454C-B3FC-BE4627290C9D","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ac4e4e7a31057a4befe50d75df65702a9276a17a","datavalue":{"value":{"entity-type":"item","numeric-id":3785935,"id":"Q3785935"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9bb9761c5c9b0c6a69c8f480d1f6b76b642f49c6","datavalue":{"value":{"amount":"+0.8101494312286377","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":"Q1853067$941776E8-92E8-415A-BE89-21D9458E985B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8ebea3e0a50c60d4bceb6a16674b36d8fc7ac459","datavalue":{"value":{"entity-type":"item","numeric-id":4734798,"id":"Q4734798"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a674ff3b46aa022c915399dac7079d87c30bd867","datavalue":{"value":{"amount":"+0.8014827966690063","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":"Q1853067$4AD4042B-D5AB-4B2D-8000-BE2A0F36FCCA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e2f7f882d2a8920f3e5b8d946343e43604f9d064","datavalue":{"value":{"entity-type":"item","numeric-id":3484389,"id":"Q3484389"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e6545277c33e9ba9a823c55eeb8cb5befaf0aba1","datavalue":{"value":{"amount":"+0.7678723335266113","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":"Q1853067$4624A348-49DD-497F-A0B2-435D2C23805D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"97008f759a24a541ffb65abbb7babbfa9fb70ff6","datavalue":{"value":{"entity-type":"item","numeric-id":1104080,"id":"Q1104080"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a23b3b4585cb09bbdb84fc22a310b900e01e8fa5","datavalue":{"value":{"amount":"+0.7645630240440369","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":"Q1853067$ECA7DD5B-20B3-47AA-BDFB-9FEECDA1C736","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a9c8cf6c2d6f95f4f0ece65a3ade55ffdfee93f6","datavalue":{"value":{"entity-type":"item","numeric-id":3217599,"id":"Q3217599"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"277bb469a45cbda8df64896fdcf9b71d1286f058","datavalue":{"value":{"amount":"+0.7573268413543701","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":"Q1853067$837A9141-37F0-41FC-8343-3B41CCEB4FE0","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On the complexity of one-shot translational separability.","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On_the_complexity_of_one-shot_translational_separability."}}}}}