{"entities":{"Q2439829":{"pageid":2450572,"ns":120,"title":"Item:Q2439829","lastrevid":57927474,"modified":"2026-04-03T03:04:10Z","type":"item","id":"Q2439829","labels":{"en":{"language":"en","value":"Constraints, MMSNP and expander relational structures"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6270634"}},"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":"Q2439829$D13BAAF6-E93F-41A3-90F1-9F4A5B5EC404","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"483c1a0157cbc954c97dd8edb24ee65dca570ffc","datavalue":{"value":{"text":"Constraints, MMSNP and expander relational structures","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2439829$AA181C09-F67F-491D-B128-E56A80AA99E7","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"7333c0099754953ca9a729afca6269f16c7ad008","datavalue":{"value":"1313.05274","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2439829$90F49CDD-7548-4FDF-A1BB-8D2F700B6BE5","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"6741da1512ed35e5400d67b6f9c31536197f3f19","datavalue":{"value":{"entity-type":"item","numeric-id":211632,"id":"Q211632"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2439829$4C3FD8D9-1506-4DC9-8102-65F7BFF727CF","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"a87e84d22579e69c48ca0a6d828473db4dde3dd6","datavalue":{"value":{"entity-type":"item","numeric-id":168579,"id":"Q168579"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2439829$14A9D3E8-CF69-4F84-B99B-ED6CDF8B4E22","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"4c390a54d5b8ac5e89f6cda6173ba0d0d0657c1a","datavalue":{"value":{"time":"+2014-03-17T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2439829$227F6C38-EED1-4F1B-961B-A547D4ED6366","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"da59308e65bc8eb216a3c5d9aab2f127a634e03c","datavalue":{"value":"https://arxiv.org/abs/0706.1701","type":"string"},"datatype":"url"},"type":"statement","id":"Q2439829$BC1730BD-0089-49CA-9D3A-E832F05C3C65","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"5b8301c17b9452fb6f6f7543f16aee5b0379886d","datavalue":{"value":"For a relational structure \\(A\\), let \\(\\mathrm{CSP}(A)\\) be a class of relational structures \\(B\\) of the same type as \\(A\\) such that a relational homomorphism from \\(B\\) into \\(A\\) exists. The girth of a relational structure \\(A\\) is the length of a shortest cycle from \\(A\\). For a relational type \\(\\tau\\) and positive integers \\(k\\) and \\(t\\), a polynomial-time algorithm \\(\\mathcal A\\) is presented such that for a relational structure \\(S\\) of type \\(\\tau\\) it constructs a relational structure \\(\\mathcal A(S)\\) of type \\(\\tau\\) with girth at least \\(k\\) and \\(\\mathcal A(S)\\in\\mathrm{CSP}(S)\\) such that for every relational structure \\(T\\) of type \\(\\tau\\) and size at most \\(t\\) we have \\(S\\in\\mathrm{CSP}(T)\\) if and only if \\(\\mathcal A(S)\\in\\mathrm{CSP}(T)\\). It is proved that the complexity classes CSP and Monotone Monadic Strict NP are computationally equivalent. For a relational type \\(\\tau\\), a positive integer \\(k\\) and \\(\\epsilon>0\\), the author gives a polynomial-time construction of an \\(\\epsilon\\)-expander of type \\(\\tau\\) with girth at least \\(k\\) of size \\(n\\) for sufficiently large \\(n\\). As a technical tool, a twisted product is introduced which is a generalization of the zig-zag product.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2439829$94F65AA8-00CF-4D6D-B2D2-C21FA41945D3","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"a09872c507729d29e1c1613e820db567c4517089","datavalue":{"value":"05C65","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2439829$344A5AA5-CE27-456A-BDB8-11B76390BCD2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2439829$11690672-A1FF-448B-86C7-7FD9D003AD99","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2439829$9B158AE7-BC3E-4F9A-B6CB-73486F84B7F4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"e01671c873d801b913451010c0981a684c101d40","datavalue":{"value":"68W20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2439829$5A51EC23-F170-4D14-9297-A0D1E5804149","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"0dd26fa594336927a7a04e8147a405d69e5da239","datavalue":{"value":"68Q87","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2439829$E1681887-409D-4DE0-8102-84C83DAB2043","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"49b058fb3bbcf2e2c0b60d335491b1fb69531246","datavalue":{"value":"05C12","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2439829$76665A2F-7431-48B9-AD3A-41186D7D1D39","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"383dddce30c1437524c5f18788fc7b4c02106463","datavalue":{"value":"6270634","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2439829$D6EB2A55-5E93-4515-82F7-375CFFB55F3C","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7b9210d6db36940a443d4266c2435b27948e64ce","datavalue":{"value":"relational structure","type":"string"},"datatype":"string"},"type":"statement","id":"Q2439829$C71CE685-8C1E-4561-95D6-8CEB55AFEBDF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a1a173748f93e4f70aa784451677e2ec88ea88e5","datavalue":{"value":"girth","type":"string"},"datatype":"string"},"type":"statement","id":"Q2439829$FF250843-9A82-443A-BBE9-5B84797A92DB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3185be620b3717b7a0242355076e9449757d2da3","datavalue":{"value":"CSP-class","type":"string"},"datatype":"string"},"type":"statement","id":"Q2439829$B2281E83-5A21-4442-923B-410BD2231176","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"78bfc749c85abbd364f01e30a5ea20bb2b4bb1ef","datavalue":{"value":"MMSNP","type":"string"},"datatype":"string"},"type":"statement","id":"Q2439829$55BB69FA-FCB0-4B3F-9347-9CB757292E85","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2363d166b5b9fc791a0d6228cc5a474e45585fdd","datavalue":{"value":"polynomial-time algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q2439829$D8A9FB3D-D778-4E7D-AF72-0C5FBBEDC44B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"527fd9bb73202f3ccbc2e98a6043eb9ea7b5dd2e","datavalue":{"value":"expander","type":"string"},"datatype":"string"},"type":"statement","id":"Q2439829$B879D0C8-F4FB-44D9-8404-5012814AFA77","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":"Q2439829$B575A5A1-66E0-4653-AEBC-C8C8C7978F1A","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"ce96d24373daa62e4d31defaff284ee3d6e949ca","datavalue":{"value":"W2041384065","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2439829$7B4B2FAC-A97A-4E63-B088-3C93997FE923","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"7b44ed555aed1fbc544de1802074fd0df13fb2c0","datavalue":{"value":{"entity-type":"item","numeric-id":1056541,"id":"Q1056541"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2439829$E34157DF-74A0-4B30-9A37-61430F7E1AFB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1c5931ab5dca72a1dc62da27774cf6861c721a7d","datavalue":{"value":{"entity-type":"item","numeric-id":2934626,"id":"Q2934626"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2439829$8025ABDA-6122-4944-94C7-D3B41AF1086C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"381fd277a2f9a07345311fee4837a5a166966422","datavalue":{"value":{"entity-type":"item","numeric-id":3424892,"id":"Q3424892"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2439829$83175EB1-3353-403D-9B05-20D32AB65F05","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"27b91fb34b309a1448e42736f924e3a5012ab649","datavalue":{"value":{"entity-type":"item","numeric-id":3253064,"id":"Q3253064"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2439829$ED5B45A6-DA96-4FF2-9AB5-3A26A452517F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"da5c6061c3f6daf7454d0e9c58daef6f441530aa","datavalue":{"value":{"entity-type":"item","numeric-id":4210136,"id":"Q4210136"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2439829$AF883ADD-D493-496A-AAAC-79B9AD06FF7D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ca4be033dc1e037b43c1538205386964bc6ef38a","datavalue":{"value":{"entity-type":"item","numeric-id":3514498,"id":"Q3514498"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2439829$E65ABCA0-A249-4471-A7AB-EB0D6270C16A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fb35deadd87315acabb99714cea9297b4fc0310a","datavalue":{"value":{"entity-type":"item","numeric-id":5936036,"id":"Q5936036"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2439829$C0EF14FB-4623-4FFD-9EC1-F33E5A722197","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7fd7e20f7a8a5b57aaaa1397122dafb976668c5a","datavalue":{"value":{"entity-type":"item","numeric-id":5540284,"id":"Q5540284"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2439829$E91178FD-1E93-4EFA-A950-939F189CB627","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"10ccf4d42c4757827ddea695c7555934bd0854b7","datavalue":{"value":{"entity-type":"item","numeric-id":1112836,"id":"Q1112836"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2439829$78C054F9-E779-4041-8841-EBEE7DE58CFA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7c40e18b1c972d5ca889339bb2a9731c4159a5fd","datavalue":{"value":{"entity-type":"item","numeric-id":814142,"id":"Q814142"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2439829$0FF81345-9443-4CEB-9223-5666E07485D0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ac46919a495b6f9ab80c70f126e6e4c268287f96","datavalue":{"value":{"entity-type":"item","numeric-id":557608,"id":"Q557608"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2439829$333C9C3A-D6C5-400A-903B-7B2298C1D411","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d1ed2ce67075a87cdb4040d4b3440a4f78bd3b15","datavalue":{"value":{"entity-type":"item","numeric-id":920104,"id":"Q920104"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2439829$DD42FAC3-81CF-43EC-B62C-FD00B4023CDE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"34ada9500bcc818699dec7a40b5563f97b9191db","datavalue":{"value":{"entity-type":"item","numeric-id":1260043,"id":"Q1260043"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2439829$FA0390C1-9888-4034-94AC-0F5651C0FCEB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"42c1bc051b288f8cda6e440dfc93179e60006f8f","datavalue":{"value":{"entity-type":"item","numeric-id":1613289,"id":"Q1613289"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2439829$A319352B-FC58-469E-AB01-4755A9EF7A59","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"3b66c9ed7a2ee16f80dcf70eb9223c03343a61e4","datavalue":{"value":"10.1007/S00493-013-2405-4","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2439829$6006845A-53C9-4695-8F35-9A8B5DD12FE0","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"96727c0fbd36dfd8c1a5eaee9df99644f7d7c44b","datavalue":{"value":{"entity-type":"item","numeric-id":5145282,"id":"Q5145282"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ceb775c34c4c25aa80b13c2d9efed963866a14b4","datavalue":{"value":{"amount":"+0.7534180879592896","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":"Q2439829$AAE68FD1-9AB8-4735-8E69-8AB7FB3C6A29","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"280d38d9dd855f89454e4a5718873e6c09c344c2","datavalue":{"value":{"entity-type":"item","numeric-id":5463349,"id":"Q5463349"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1608fddfb6a400ba3f616d77c97dc76402276386","datavalue":{"value":{"amount":"+0.7468321919441223","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":"Q2439829$225F6B30-3294-493B-80E6-FF22AAB29DD6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"913bf2f44a6b812d5f0bc1843b2b2553d02fe725","datavalue":{"value":{"entity-type":"item","numeric-id":2902910,"id":"Q2902910"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"63a5be9721e2bb4aa022506f4a35b178b8a9a62d","datavalue":{"value":{"amount":"+0.7286941409111023","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":"Q2439829$CC915197-676D-4161-A8DA-FA128BDDFE55","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b34a42074bc0788f0e2e10ed398d7b64830bb0df","datavalue":{"value":{"entity-type":"item","numeric-id":4973888,"id":"Q4973888"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cf5186b3281380c9af22c9b56092b9b08cefd5b9","datavalue":{"value":{"amount":"+0.727816104888916","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":"Q2439829$22B61D5B-AC8E-4533-9492-E89EEBA59302","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7b363ffb3ce288ee0fc861a0f1549f1d8a0a508b","datavalue":{"value":{"entity-type":"item","numeric-id":3002825,"id":"Q3002825"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cde345ff7c884d59a19f8d28fa5373400630e053","datavalue":{"value":{"amount":"+0.7254853844642639","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":"Q2439829$E488313E-9A34-4449-B28E-9B815680B543","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2439829","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2439829"}}}}}