{"entities":{"Q1716008":{"pageid":1726749,"ns":120,"title":"Item:Q1716008","lastrevid":57498585,"modified":"2026-03-31T04:27:41Z","type":"item","id":"Q1716008","labels":{"en":{"language":"en","value":"Hardness of almost embedding simplicial complexes in \\(\\mathbb {R}^d\\)"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7007883"}},"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":"Q1716008$0D0F331A-C91E-4637-8589-B01F1973A64D","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"a8d46e5fbb55a75fc14d3e36acd46b06a1e9d323","datavalue":{"value":{"text":"Hardness of almost embedding simplicial complexes in \\(\\mathbb {R}^d\\)","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1716008$985AD7EA-6952-4D43-8EBB-94D4C5B24588","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"51a4895f84ccd42d4d773b2161195253247b5cb5","datavalue":{"value":"1415.57016","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1716008$5E701343-72A9-4DD2-9819-B123B8481CA8","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"88afbc92a3c9080b5210385edb31257432cc65f4","datavalue":{"value":{"entity-type":"item","numeric-id":249463,"id":"Q249463"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1716008$DBE619A7-FE2C-477F-8969-3DAD5F2AA5F4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"0fc7bafb4d528dffe8dc01719acc9dcfb714ebcb","datavalue":{"value":{"entity-type":"item","numeric-id":1295254,"id":"Q1295254"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1716008$A3469732-691C-48EF-AD30-EBD1F8E08A6F","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"b6f367138a9ac2b85113cfed5a6fd5bedcc8944c","datavalue":{"value":{"entity-type":"item","numeric-id":178842,"id":"Q178842"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1716008$CF5F7680-E1E0-4ADB-B10F-FF80E366D55F","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"8f9b4bd3140ebb78985a05d940c7570d35999b10","datavalue":{"value":{"time":"+2019-01-29T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1716008$293195DB-B523-415B-8FCD-07885D971257","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"b9f9466a10d7756592e6dbbbeec9f8ae6d3d478e","datavalue":{"value":"https://arxiv.org/abs/1703.06305","type":"string"},"datatype":"url"},"type":"statement","id":"Q1716008$E76F0D50-8475-437E-B9B0-9690DD95579F","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"d75c4e4fe6af99d319328fdcbb85c83f1ca462d5","datavalue":{"value":"The authors introduce notion of ``almost embedding'' of a finite $k$-dimensional simplicial complex $K$ in $\\mathbb{R}^d$ and discuss related algorithmic problems. In case of embeddings of $|K| \\to \\mathbb{R}^d$ this problem has been treated in [\\textit{J. Matou\u0161ek} et al., J. Eur. Math. Soc. (JEMS) 13, No. 2, 259--295 (2011; Zbl 1208.68130)]. If $\\tilde{K}$ denotes the simplicial deleted product of $K$ and $f:|K| \\to \\mathbb{R}^d$ an almost embedding, then we have an equivariant map $\\tilde{f}: \\tilde{K} \\to S^{d-1}$. The main result of the paper says that under some assumptions we may have $K$ and an equivariant map $\\tilde{K} \\to S^{d-1}$ but not an almost embedding of $|K|$. These assumptions are the following: P $\\neq$ NP, $d, k \\geq 2$ and $d=3k/2 + 1$. From the algorithmic point of view the problem of recognition of almost embeddability is NP-hard.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1716008$81040064-9EC2-4704-AAAA-61D6CC4955AB","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"3dc4ae7cbead5b7d81674272fcad45b69891ae67","datavalue":{"value":{"entity-type":"item","numeric-id":590844,"id":"Q590844"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1716008$C3DF2063-5E3D-4774-AF4C-249F1461774B","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"9a80fd41512d83ea0e0013137710271fe926464e","datavalue":{"value":"57Q35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1716008$EC67F92C-A5C1-410F-86AD-16883790D3FF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1716008$BE253143-D232-48EB-9450-D6ABBE0F207A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"e669b60521e14398c1f2263792cea32c3a9da254","datavalue":{"value":"05E45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1716008$5ABA453C-C7C1-48B1-9689-D84DE9869C6B","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"1f89adcad33d8a7a7237a7ce1bf6f77d033c29d6","datavalue":{"value":"7007883","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1716008$798FA207-D5A4-46C8-A2BD-6C27DADA2845","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"150af7cdcddd88dd45e94cda17cd2a38a1006fa8","datavalue":{"value":"almost embedding","type":"string"},"datatype":"string"},"type":"statement","id":"Q1716008$114D6734-D786-4748-8DA2-EA6EB665B122","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8f12ea105addea4e52f9511695748975bd61a49c","datavalue":{"value":"NP-hard","type":"string"},"datatype":"string"},"type":"statement","id":"Q1716008$11B13338-3DF5-4E7C-BE52-C44063C925F8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"15a090d49bf3cc82babef681634cbda48d7a6fb3","datavalue":{"value":"equivariant map","type":"string"},"datatype":"string"},"type":"statement","id":"Q1716008$30098E46-A902-4457-BC40-1B53EDD97AB8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"181c2212c90e8b5158b1da877a1ca9e811caca38","datavalue":{"value":"PL embedding","type":"string"},"datatype":"string"},"type":"statement","id":"Q1716008$1BE77E03-ABAC-42A0-81BF-406A64C56BB6","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":"Q1716008$1BD6B55F-10F2-4E1E-9BFA-20395EFE87D6","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"bf60074bd01960ca11f0b6cafab06df3079ab186","datavalue":{"value":"W2951644490","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1716008$086185C2-B41E-4A7B-9F74-D9557195C1ED","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"dd2dfa10b90e69c01b3b742ddaf498f9516d1f32","datavalue":{"value":{"entity-type":"item","numeric-id":2952027,"id":"Q2952027"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1716008$D42F74A6-1309-4C98-9059-2372649D7368","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0d7eaef25da286a32202d0b89dc7e635541f1a2d","datavalue":{"value":{"entity-type":"item","numeric-id":4604377,"id":"Q4604377"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1716008$CF4E55DE-B32E-48D2-A87B-FB05B5F2A45C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b8e987bd0ebd771601f757e3dd325e456297eb46","datavalue":{"value":{"entity-type":"item","numeric-id":1587508,"id":"Q1587508"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1716008$BDF29003-FBF8-40BB-9A26-E45D73F82C09","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c8cb5187876716610fff6828ac06d6380f2f6fbf","datavalue":{"value":{"entity-type":"item","numeric-id":2358826,"id":"Q2358826"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1716008$A6CE0583-952F-4BDE-8A7B-6717B4C1D91E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e9f2201e6e1c18e3d7623557a829f7b53cc6e6ec","datavalue":{"value":{"entity-type":"item","numeric-id":2524661,"id":"Q2524661"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1716008$55260759-C6CC-49C2-B90A-E2BBFEDB593B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"46bdd2418b81001d40f2574e6a6bef82d6007421","datavalue":{"value":{"entity-type":"item","numeric-id":2362643,"id":"Q2362643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1716008$C20CE541-353E-40EB-8385-87A2B301A836","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1dc1147e4e7c9ea02361355191ea26e0c40586da","datavalue":{"value":{"entity-type":"item","numeric-id":1901645,"id":"Q1901645"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1716008$80F4FE23-C875-478A-BB84-5ACAB58D779F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"234b5243d0436a1b042da9dba75ccb78fb7589aa","datavalue":{"value":{"entity-type":"item","numeric-id":4604384,"id":"Q4604384"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1716008$2E166A50-6445-438B-9A39-352371221CD9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bf94f0f32aa4c6c305a781d96f72e89877c6ad2b","datavalue":{"value":{"entity-type":"item","numeric-id":2498030,"id":"Q2498030"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1716008$4BF49FBA-DA92-4883-876A-7AE6A8D81F4C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7bff4da6c1d6da2ecd996a7eb49167ae1e3533b0","datavalue":{"value":{"entity-type":"item","numeric-id":5584509,"id":"Q5584509"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1716008$F66E18D1-CA97-4B85-997A-D2B0D08415FF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4363b5733d4f9006cef0d597d0b1dae62084944c","datavalue":{"value":{"entity-type":"item","numeric-id":1361809,"id":"Q1361809"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1716008$3F1B9CAF-780E-41D9-8E54-B4F0BB2E3E55","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"234bd39e6c43ef9b2c800934480abb5b01cfa147","datavalue":{"value":{"entity-type":"item","numeric-id":621847,"id":"Q621847"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1716008$D9112F9E-C39F-4331-91FB-85638F0FD813","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"55ca72696343cf30d6a11bb5ca83f8a775848542","datavalue":{"value":{"entity-type":"item","numeric-id":1198636,"id":"Q1198636"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1716008$7F0E5E32-3E1F-45DD-8632-2482103A5C70","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0e573a29076e53b70e412b350197a2b91dc67e40","datavalue":{"value":{"entity-type":"item","numeric-id":1295310,"id":"Q1295310"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1716008$FF579492-0661-4378-BF46-C3EFC90D4CAC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1eea7f6362377d964dbcc131a7d8877819bdaa20","datavalue":{"value":{"entity-type":"item","numeric-id":770761,"id":"Q770761"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1716008$EFC89FEF-27FF-4945-B349-B2D494DE6F25","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ed762a45342ce0ecc975dbcbad286b8f890fb188","datavalue":{"value":{"entity-type":"item","numeric-id":3923266,"id":"Q3923266"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1716008$D308F2FF-E10F-4A99-A320-F6EC955AD6D5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2d0ecdc73a067215fa55ac8eb0224f02bf4027a6","datavalue":{"value":{"entity-type":"item","numeric-id":5301264,"id":"Q5301264"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1716008$9866BE7B-82D6-427B-A9B6-C3C10C7E6CDC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c9f7296ec80ebde687278a2a2636a3ffc92b4a39","datavalue":{"value":{"entity-type":"item","numeric-id":4684242,"id":"Q4684242"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1716008$34C9B38A-4181-4A0B-88D1-FE2D37C23B07","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0bf12645df80559abc0e293f62c72f98add1ffb1","datavalue":{"value":{"entity-type":"item","numeric-id":1409758,"id":"Q1409758"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1716008$AEF9D1AA-DA53-49AB-81F8-2DDBAE952D49","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d2ffcb76585c54d4afc4b086e55a6a9b58314787","datavalue":{"value":{"entity-type":"item","numeric-id":4069522,"id":"Q4069522"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1716008$F81550D5-D4F2-4147-A65A-FD85EBCBD02A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"40e847dc1c374d6644afd72392be7c29f4feb7fa","datavalue":{"value":{"entity-type":"item","numeric-id":2525818,"id":"Q2525818"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1716008$412B53F5-8508-4EAA-912B-EE52FA0CF3D7","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"1d46db1a08423b1a8538d0cadd09c015f417aac6","datavalue":{"value":"10.1007/S00454-018-0013-1","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1716008$D6D51248-7DED-4FD0-9CF7-0A190239A2E8","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e1d6abacdcd7f7a13646bb4f2d7a8e310efcb90d","datavalue":{"value":{"entity-type":"item","numeric-id":621847,"id":"Q621847"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3dc363e3cceeed08cb5450f79b591f00c9b3671e","datavalue":{"value":{"amount":"+0.8938010334968567","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":"Q1716008$286A351C-C585-4925-9B87-57206A40F41F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0fb085bb47cdc73bf08108d059fcb794b24852ef","datavalue":{"value":{"entity-type":"item","numeric-id":4633898,"id":"Q4633898"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f1ac8b853a2f297ea8cd3351726b4a5c081445d0","datavalue":{"value":{"amount":"+0.8878704309463501","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":"Q1716008$B87CB19B-16AC-403F-9A2D-92512D1A3241","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"178e920fd6d338a462445322abc682b7be72f78d","datavalue":{"value":{"entity-type":"item","numeric-id":4607974,"id":"Q4607974"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"49dae746fe5d4ef7fe2c9f964cf9b7d98d9a71f0","datavalue":{"value":{"amount":"+0.8367314338684082","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":"Q1716008$064312B9-2FEE-4546-995E-B6BC74F0A07F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"775be832a65e07901e8d67d776ee4e7e365601d2","datavalue":{"value":{"entity-type":"item","numeric-id":5133975,"id":"Q5133975"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6b766ed2f3d473e9b4473676c3751767853892b1","datavalue":{"value":{"amount":"+0.8131672739982605","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":"Q1716008$F18472E0-7071-4485-ADE2-57CE0A0513B5","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1716008","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1716008"}}}}}