{"entities":{"Q463039":{"pageid":464806,"ns":120,"title":"Item:Q463039","lastrevid":62013747,"modified":"2026-04-11T03:12:04Z","type":"item","id":"Q463039","labels":{"en":{"language":"en","value":"Permutation reconstruction from differences"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6360678"}},"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":"Q463039$75886066-7705-4455-93EA-FB5A444F7035","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"621e8c2ab3bd27ae69c01312f005683bbaf8f3c5","datavalue":{"value":{"text":"Permutation reconstruction from differences","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q463039$A51B14B2-5139-4DDE-9E18-8C95C6EB8AD8","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"8ed7bf3885e764c303b9950724ac2e8e0b79a33c","datavalue":{"value":"1298.68098","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q463039$15622838-7937-44EC-B53C-7F481E581758","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"2b7ae2d879feca7dd177f05c20300c073c6ef917","datavalue":{"value":{"entity-type":"item","numeric-id":463038,"id":"Q463038"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q463039$F30526CA-B683-47ED-8AF2-29567BE8EC7E","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"ebc7441ecfd9ecfa38d48ddc4b2adb39ac7d7000","datavalue":{"value":{"entity-type":"item","numeric-id":161296,"id":"Q161296"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q463039$DA2D0F89-57B6-45D6-BE5E-9917675CC336","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"19223fa13371e3ce1b1dd08c8b63557fc81ef3f8","datavalue":{"value":{"time":"+2014-10-23T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q463039$17D830EC-3C91-4474-A766-7355224C54F0","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"dcf70b028df2d3af54f6f6c8c057c9a88dd16abb","datavalue":{"value":"https://arxiv.org/abs/1410.6396","type":"string"},"datatype":"url"},"type":"statement","id":"Q463039$FC058845-7F23-4AA5-BFE0-12C411E8CE58","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"d4a2e9547c352d6e0c289e66d80d555daff25aff","datavalue":{"value":"http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p3","type":"string"},"datatype":"url"},"type":"statement","id":"Q463039$599520EA-D9F1-4B5E-A88C-D97E2351878B","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"0f3c3b43681d4dc6401cc8d56a6b996c66ded0cf","datavalue":{"value":"Summary: We prove that the problem of reconstructing a permutation \\(\\pi_1,\\ldots,\\pi_n\\) of the integers \\([1\\ldots n]\\) given the absolute differences \\(|\\pi_{i+1}-\\pi_i|\\), \\(i = 1,\\ldots,n-1\\) is \\mathsf{NP}-complete. As an intermediate step we first prove the \\mathsf{NP}-completeness of the decision version of a new puzzle game that we call \\textit{Crazy Frog Puzzle}. The permutation reconstruction from differences is one of the simplest combinatorial problems that have been proved to be computationally intractable.","type":"string"},"datatype":"string"},"type":"statement","id":"Q463039$856E2B1C-BCB9-413B-95E7-FBE44AA49778","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q463039$6813418C-8940-4407-9F15-E77A98A408D0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6247f04fad65d359a20e559b3e9499d6219d492e","datavalue":{"value":"05A05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q463039$20A62C0E-2A85-45C2-8CFF-BDFB82E2221B","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"43b69bbb7a74729a41df16712574faff4257f03c","datavalue":{"value":"6360678","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q463039$52DC9E72-1A70-4D50-ADE5-D0A8802BB2E7","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"173da7ea66c852016bd5e756f534ee49413e7193","datavalue":{"value":"permutation reconstruction","type":"string"},"datatype":"string"},"type":"statement","id":"Q463039$D2C39912-0C7D-4344-BA0D-220986B36397","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cf1bbad404b660dcc4f7e1f74269a25b269f6b2f","datavalue":{"value":"NP-completeness","type":"string"},"datatype":"string"},"type":"statement","id":"Q463039$E3E62719-489E-464A-8DD7-F14F0171CB6B","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":"Q463039$142A2A65-9BBE-4386-A090-0E93DF0FC8F9","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"d35ad894e5604e261af3c916c955f67cca24b1b1","datavalue":{"value":{"entity-type":"item","numeric-id":3574125,"id":"Q3574125"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q463039$AC4A4EE4-A59C-449C-8AC6-FBACA0BA837E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3fa97f0110ceefce3316c5fbe9c21778948ad688","datavalue":{"value":{"entity-type":"item","numeric-id":4742820,"id":"Q4742820"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q463039$0B260E4C-912D-4462-BB32-A653C3FF8E14","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"62d088c0ead3e27126e7b16f155dbba58e04788c","datavalue":{"value":{"entity-type":"item","numeric-id":1010923,"id":"Q1010923"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q463039$DD6E5A87-2828-4E25-8785-93390E90610D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"58079b4c9bcc158afe9f026057f563492b9a4b0f","datavalue":{"value":{"entity-type":"item","numeric-id":2500985,"id":"Q2500985"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q463039$B700B772-F043-4EF3-A644-9D583812AF11","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a34f4e568c2469f8063f69f8c16802976e475eb9","datavalue":{"value":{"entity-type":"item","numeric-id":3392273,"id":"Q3392273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q463039$FC3F6041-2064-4BB0-B681-D1E75B4CE222","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1352f5455377dc4215eb400b3ed510333c37452a","datavalue":{"value":{"entity-type":"item","numeric-id":2501000,"id":"Q2501000"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q463039$6255735F-A6E2-42C7-B463-4B9A6405DE4F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2ad2fe8dd86fee87642683d5794ea0cbe53231bb","datavalue":{"value":{"entity-type":"item","numeric-id":3259049,"id":"Q3259049"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q463039$E177E48F-8B1A-4CDD-A347-F68DBEEDE6C1","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"63088c52281647c35a4454e3b116ac293fec0933","datavalue":{"value":"bafkreigf2e6qrjguors7qmthe7ppvnb7orwj3rjacwe7ebqwnu6kajmaaa","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q463039$78C94758-393F-44CC-B589-93D0ABCE3370","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"30772b45dc5e6dd8dba37a543bb752062ffc90b3","datavalue":{"value":{"entity-type":"item","numeric-id":2501000,"id":"Q2501000"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0aaf034a34f539e527a4dc091cac58f2ec90f228","datavalue":{"value":{"amount":"+0.7163722515106201","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":"Q463039$7C0EC1C1-BE2D-4D2B-B201-95919B6BB227","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b28c36ce21dea847635da325c3d0dc0d6b8053bc","datavalue":{"value":{"entity-type":"item","numeric-id":290110,"id":"Q290110"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a262de34bac20d018cd7cf67051f4f406dfa3003","datavalue":{"value":{"amount":"+0.6983079314231873","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":"Q463039$26560349-9BAA-4C2D-8C7F-DD7B08A5B8BF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b024ea04c8ff31d26227eacaa8004cb7f16fd1aa","datavalue":{"value":{"entity-type":"item","numeric-id":1603693,"id":"Q1603693"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"409d45a2fd5cb1c72c5824c6cc848e7bab9f70a4","datavalue":{"value":{"amount":"+0.6965382695198059","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":"Q463039$AE34BCBD-3C4A-46A4-9B4E-9358296F31F0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1ccabe739b1db0b8d046f5352ab5406661366adb","datavalue":{"value":{"entity-type":"item","numeric-id":1637231,"id":"Q1637231"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2643d069053b6df3b892fdb40449381acc912d5c","datavalue":{"value":{"amount":"+0.6905715465545654","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":"Q463039$3660A94B-D674-4947-B30D-3B6B3D676BD8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b4387093a0ad35b5f94e129048a12d8af541c2d3","datavalue":{"value":{"entity-type":"item","numeric-id":5310238,"id":"Q5310238"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7210e69d07dbb602850f895df3c834606def58fa","datavalue":{"value":{"amount":"+0.6895557045936584","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":"Q463039$F6AA6291-573D-4F69-A531-F5B3AEEDA56B","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Permutation reconstruction from differences","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Permutation_reconstruction_from_differences"}}}}}