{"entities":{"Q1930164":{"pageid":1940906,"ns":120,"title":"Item:Q1930164","lastrevid":69324228,"modified":"2026-04-13T06:14:37Z","type":"item","id":"Q1930164","labels":{"en":{"language":"en","value":"Complexity and algorithms for Euler characteristic of simplicial complexes"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6124225"}},"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":"Q1930164$22349D91-D1D4-4BFF-8AA5-94B3955455BB","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"ab091f6fda6044c400d2a5577bc9fc5db333f201","datavalue":{"value":{"text":"Complexity and algorithms for Euler characteristic of simplicial complexes","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1930164$5094E466-83AB-4004-A71D-0CE700E957EF","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"61270f53e3f16201b9177f4e32b6a2d66aebc2ec","datavalue":{"value":"1263.68052","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1930164$5D59267F-D6F6-48F4-8009-B33D29FC73B2","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"d572a68e34b7742d433468b9de809ae89da57a15","datavalue":{"value":{"entity-type":"item","numeric-id":347117,"id":"Q347117"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1930164$D11C5E11-7156-4BAC-AB8D-2C120F012EA9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"ead42232ae2dde187e798e1f861e44a8146dfb7d","datavalue":{"value":{"entity-type":"item","numeric-id":321290,"id":"Q321290"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1930164$A4D2B49A-D6CC-40B2-BAA7-28E946BFCB60","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"ea72303f92787da89554ee5fa15621068821a762","datavalue":{"value":{"entity-type":"item","numeric-id":99061,"id":"Q99061"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1930164$61414F8E-1AC4-4044-A92E-19EE2733805E","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5f73384387181e740d0320d4931fc1cd66aeb99c","datavalue":{"value":{"time":"+2013-01-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":"Q1930164$D2820F91-90E5-41AD-87F2-C51309419E72","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"954f3c9db5e5b958894bebba6d9be52e44b9c80e","datavalue":{"value":"https://arxiv.org/abs/1112.4523","type":"string"},"datatype":"url"},"type":"statement","id":"Q1930164$83C5138C-71A7-4B0C-B07D-19CF995DD51E","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"9d08aa2948987375ece22099c0221c1180fa8263","datavalue":{"value":"An abstract simplicial complex \\(\\Delta\\) is a subset of the set of all subsets of a given finite set (the vertex set \\(V\\)) that is closed under taking subsets. The subsets of \\(V\\) that are in \\(\\Delta\\) are called faces of the complex \\(\\Delta\\). The inclusion-maximum faces of \\(\\Delta\\) are called facets of \\(\\Delta\\).  Let \\(\\Delta \\) be defined by two sets: the set of vertices and the set of facets. Actually, with such input, the problem of computing the Euler characteristic \\(\\chi (\\Delta)\\) has not been considered before in terms of complexity theory. The authors prove that this problem is \\(\\#\\text{P}\\)-complete by reducing to it the \\(\\#\\text{SAT}\\) problem (of counting the number of satisfying assignments of a given Boolean formula) well known to be \\(\\#\\text{P}\\)-complete.  As a corollary they obtain a known result due to \\textit{V. Kaibel} and \\textit{M. E. Pfetsch} [in: Algebra, geometry, and software systems. Berlin: Springer. 23--48 (2003; Zbl 1027.65032)] stating that the problem of computing the \\(f\\)-vector of \\(\\Delta \\) is \\(\\#\\text{P}\\)-hard.  Furthermore, the authors present two algorithms for computing \\(\\chi (\\Delta)\\). The algorithms are presented in two forms: one is in terms of commutative algebra (based on monomial ideals) and one in terms of the complex \\(\\chi (\\Delta)\\) itself.  Finally, the authors present the results of a set of simulation experiments to show that the two new algorithms run faster than previously known Euler characteristic algorithms.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1930164$6602CFD1-57B7-4E3C-9BFA-5CB61F3E94CB","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"d954a68edf0d8701e0810168bf45596d167285bb","datavalue":{"value":{"entity-type":"item","numeric-id":917980,"id":"Q917980"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1930164$D0F95480-DF02-4E87-9C07-7F25AB99F061","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1930164$D7DFC1C4-1AAA-42E6-9893-1BAFC715C7CF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"3261dadc98deaaa969a534e2a2cb92fd4aa565f7","datavalue":{"value":"13P99","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1930164$5EAC102D-28D3-4FB5-ABC7-D35B0A9E316D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5adb849ecb2203541270370c9265ac70cda6203c","datavalue":{"value":"13P25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1930164$0F411BBA-8C33-47E8-A7A3-F6AFBAE8CF3D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5408cf94c8585439fdc1c7736fd361405fcf2194","datavalue":{"value":"13F55","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1930164$7EF26AB4-560F-486A-85A1-B35D7ACFB64C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6be78f1bad1f2f19058dbde65eb124c0430a7d27","datavalue":{"value":"68W30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1930164$8D003FBD-56F2-4465-BD5F-C240F3865575","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"e669b60521e14398c1f2263792cea32c3a9da254","datavalue":{"value":"05E45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1930164$A364EC20-74DD-4D17-8DB5-B85CE875E492","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d441cca05a352782e8c8e9c285fa1f8dd5752682","datavalue":{"value":"55U05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1930164$0A366739-A470-4499-AE1F-CCCCEB41952A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6d3abef3a32e485f75d172220e01cf64fe802dde","datavalue":{"value":"57-04","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1930164$231DC72E-0801-43AC-AE8D-38D2E6E72D81","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"d41a7131b1cff655f496b8f79d3857dcb6c7dfa9","datavalue":{"value":"6124225","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1930164$86CAB643-F7F2-4438-9245-A994A1CA2259","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"dae6b73647501cddc60bea81c63e58401d0164fd","datavalue":{"value":"Euler characteristic","type":"string"},"datatype":"string"},"type":"statement","id":"Q1930164$81FDFD58-0414-4DD0-9150-53BEA7E4F41C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"152b51a76bc3f2ffd0d6ea5cc70d9b732a88636f","datavalue":{"value":"monomial ideal","type":"string"},"datatype":"string"},"type":"statement","id":"Q1930164$09A4E34B-C45F-4514-AB55-4042074451B0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"78b826843ab20a87c9262e0d558d414868bdd4a5","datavalue":{"value":"simplicial complex","type":"string"},"datatype":"string"},"type":"statement","id":"Q1930164$E29440D2-BC49-423D-BD65-3E38AE63A7D9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2b56af9cf500bb84504d0b9fd9093fc629d3c32c","datavalue":{"value":"\\(\\#\\text{P}\\)-complete","type":"string"},"datatype":"string"},"type":"statement","id":"Q1930164$C763F401-EF2E-4D22-BE3D-2E26C9B383BD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2ba0cc3f7aaac8445724ef309c9eecb57f5a563d","datavalue":{"value":"computational complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1930164$ECCA8973-67FA-4D6D-877A-9CADD2DBD0DE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d607627523840bd0bf4407097f29a3a99ef4a0a8","datavalue":{"value":"algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q1930164$967168C8-5A26-47D2-8A3F-FE7D47762925","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":"Q1930164$3D3A138C-C134-4888-A1D0-46234045EB7E","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"f66b4b8b1a48a175e3415ad771f2db80ecb8df25","datavalue":{"value":"W2963061445","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1930164$F4686DBA-84B2-4FEA-B4E7-2A7B2178832C","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"65e17b57fd9053a56b8d14bd4fc3914c70b16369","datavalue":{"value":"Q60246122","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1930164$0143C7D4-0ED2-43A3-AD9D-57C8BBB7BD21","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"661c86e1c6e7bec4fcec8a719cfe65d26736fd85","datavalue":{"value":"10.1016/J.JSC.2012.07.003","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1930164$870A8763-5250-46A4-A901-FC2CCF96C02E","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9453df3606843d6d2ea942f2c25980d330f5483e","datavalue":{"value":{"entity-type":"item","numeric-id":1017924,"id":"Q1017924"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"65fa785dbe410dbbe3d0dc1f62ff9b163622dd42","datavalue":{"value":{"amount":"+0.7199811","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1930164$5D3C2AA1-3F69-4F1E-B4E3-37BCE8F4E497","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"18377a99f58a11bbecd89eaf08444529a168c0ac","datavalue":{"value":{"entity-type":"item","numeric-id":6132729,"id":"Q6132729"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3fdaf6cc418def047fdcf77be34c69015be4f0ed","datavalue":{"value":{"amount":"+0.71815205","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1930164$47E783BE-BB50-4CFE-82BF-08B96887372B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1bc616438c7d4119b49389c03873bc7977af16c0","datavalue":{"value":{"entity-type":"item","numeric-id":1380805,"id":"Q1380805"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fb2360366e826f38a919edc6b2056a729744b5db","datavalue":{"value":{"amount":"+0.69764555","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1930164$37644215-32A7-4AE4-93B4-E90325B44D44","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"da7777a397133df5cbffaa0d7025a8d4f9dbed33","datavalue":{"value":{"entity-type":"item","numeric-id":905846,"id":"Q905846"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b06a04e15cab59fd6f88d397916cf56133d3b94d","datavalue":{"value":{"amount":"+0.6952797","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1930164$7C6A48A2-EAF6-4396-870D-6121D2BB87D4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1428ffa5e1d1aeb576fd7b1c7c910edbe272202d","datavalue":{"value":{"entity-type":"item","numeric-id":5383970,"id":"Q5383970"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0738676b22054f31895c16e1d091c70f6ece65b1","datavalue":{"value":{"amount":"+0.6944648","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1930164$9A729109-45FC-4ABB-A5CD-DE6326436C5D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c0090835c2dc7e323d20e6cda76e79f42001c227","datavalue":{"value":{"entity-type":"item","numeric-id":3677173,"id":"Q3677173"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9c028b0261b8d7f3d4aa81b1c38a5d1f10d02a9d","datavalue":{"value":{"amount":"+0.6934395","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1930164$AFD1D075-16F4-4286-B152-E97E06E5092D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"12052343980e2f20407a42193b19abef6a08d602","datavalue":{"value":{"entity-type":"item","numeric-id":4418120,"id":"Q4418120"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b5bcfb48d2ef8d3bd79ea3813a40898b9677b09f","datavalue":{"value":{"amount":"+0.6853849","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1930164$106E306C-594C-4D65-9D5A-91D75D94EF12","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2174f9a70ea2c6c840c802246a697b0002be6873","datavalue":{"value":{"entity-type":"item","numeric-id":1334609,"id":"Q1334609"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8e66456b027ae64b6f583d6f4b1b64d41db706b8","datavalue":{"value":{"amount":"+0.6849175","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1930164$4F7AE1EE-D95A-498D-8530-01FC16F8C07D","rank":"normal"}],"P1635":[{"mainsnak":{"snaktype":"value","property":"P1635","hash":"2ec6b6dd797252882d01bf525bff56ea02781ef7","datavalue":{"value":"journals/jsc/RouneS13","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1930164$B73D9F19-FF81-4405-B0AC-C6A470621320","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Complexity and algorithms for Euler characteristic of simplicial complexes","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Complexity_and_algorithms_for_Euler_characteristic_of_simplicial_complexes"}}}}}