{"entities":{"Q1758159":{"pageid":1768901,"ns":120,"title":"Item:Q1758159","lastrevid":51591641,"modified":"2026-01-18T23:17:35Z","type":"item","id":"Q1758159","labels":{"en":{"language":"en","value":"Complexity of Gr\u00f6bner basis detection and border basis detection"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6103618"}},"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":"Q1758159$4170A8EB-4BEC-48E8-AB71-3DD877FD1AF3","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"7daf5199ac1e8c6ad01f760f11635d138393f0ec","datavalue":{"value":{"text":"Complexity of Gr\u00f6bner basis detection and border basis detection","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1758159$880BCCB2-1040-4499-8B53-854D60E22B94","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"0a2788390ca4708f7395f5da11d06b88996c9c16","datavalue":{"value":"1258.13029","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1758159$70D2E309-4AFA-4716-9F5B-6AF551D52AD7","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"0312613e6359e12e164c3669d20a150884f16aca","datavalue":{"value":{"entity-type":"item","numeric-id":1758158,"id":"Q1758158"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1758159$7E9CF1A1-1FB2-4799-A19D-B873E0820BB7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"1e641bf33a0a582a251f02771224b2179b84d25c","datavalue":{"value":{"entity-type":"item","numeric-id":387707,"id":"Q387707"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1758159$9136CBF2-4F11-44CC-91A2-45A995A04EE1","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f3c424cd94a60f9664f9fb69cc6027e75cc7ff3f","datavalue":{"value":{"entity-type":"item","numeric-id":123643,"id":"Q123643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1758159$B1A7FABA-8FB8-4580-BFDA-0C11F1E001C9","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"1fd40b453552197bf6992e0512f747c68abfc621","datavalue":{"value":{"time":"+2012-11-08T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1758159$A01586F8-1431-48CA-AAA8-C69F476E0A76","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"5b7452c01dc41eeb3129855a6973f9a705613533","datavalue":{"value":"The authors introduce the border basis detection problem (BBD) which is to decide if a given set of polynomials is a border basis with respect to some order ideal. A similar problem is the Gr\u00f6bner basis detection problem (GBD) which is to decide if a set of polynomials is a Gr\u00f6bner basis with respect to some term order. GBD was shown to be NP-hard by \\textit{B. Sturmfels} and \\textit{M. Wiegelmann} [Appl. Algebra Eng. Commun. Comput. 8, No. 4, 257-263 (1997; Zbl 1055.13503)]. In the present paper the authors show that BBD is NP-complete, that is, NP-hard and NP itself, by relating it to the 3,4-SAT problem.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1758159$756CB078-375D-40F4-AC91-F0AC07B4D671","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"b38130ed9909b8c7bacb0e241b601af49d4e19ad","datavalue":{"value":{"entity-type":"item","numeric-id":252472,"id":"Q252472"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1758159$9CCC104E-0ECD-4A81-AC71-54DB9078577B","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"173b0c3afec7c4f9f987722665cc7bdb6b8f5813","datavalue":{"value":"13P10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1758159$E2582ED8-9472-4EBD-B51A-70B6845BEE5F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1758159$568451F1-8F59-4EB8-AB67-AD71B7362804","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b4346faa01bb5fb0576370374d6456afd58d5666","datavalue":{"value":"68Q15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1758159$22E701B5-E6A9-419F-9D28-1175E40BD8D1","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"1512f15312f8b2b6e6de6aeea6d2523f576ed08d","datavalue":{"value":"6103618","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1758159$704710E0-A092-4451-BCCD-4C8050C1AB35","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"99c239dc77a316f7da47f9d2d7c645993f6cd8d7","datavalue":{"value":"Gr\u00f6bner bases","type":"string"},"datatype":"string"},"type":"statement","id":"Q1758159$705DDB5C-FB6A-494C-B37B-1C952A3A6750","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4d069b165c81f5f571be278e4bf8666671edfc28","datavalue":{"value":"Border bases","type":"string"},"datatype":"string"},"type":"statement","id":"Q1758159$F3D4E801-C6EA-4D24-984C-5B523EC35969","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c5206d4dce6a163eafa029a63a1fb2a44925dc13","datavalue":{"value":"Complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1758159$9C980BF4-A754-47A2-9F4C-7B4CBCEE2564","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9c30b82c6ce820ba86eea0ca340d47b11c27534b","datavalue":{"value":"NP problems","type":"string"},"datatype":"string"},"type":"statement","id":"Q1758159$08A4E641-CA37-4B3B-8FF2-805C4705A415","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":"Q1758159$4FA580F9-5313-473C-8CED-4B76DFFDA67F","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"1c70182ff646eee18668cb585079962b96e68cd0","datavalue":{"value":"https://doi.org/10.1016/j.tcs.2012.08.002","type":"string"},"datatype":"url"},"type":"statement","id":"Q1758159$ED1BE6ED-8536-4D2F-987B-A706A46A23E9","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"7e5daaa6a39421744d7a36534ff6b5e924c697d1","datavalue":{"value":"W2048364901","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1758159$04B32C2C-E561-4492-AB56-8ADE8F4001AF","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"df0782975ec5ec1f2719a7f9b1dec11f85849f65","datavalue":{"value":{"entity-type":"item","numeric-id":4317754,"id":"Q4317754"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1758159$A64391CA-6614-4823-9246-47C1806520E0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"47106273311998ec51a50bfc0d9e1c490304311b","datavalue":{"value":{"entity-type":"item","numeric-id":5254148,"id":"Q5254148"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1758159$12C42B5B-E1D0-4046-89FE-364B7F1E5E98","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5a6340c3aa9cd67064a8033bdc4924d285770a5e","datavalue":{"value":{"entity-type":"item","numeric-id":3806684,"id":"Q3806684"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1758159$3CBC132D-BA3F-4763-8F2F-619202A5D9D7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2acfaca0cc576cff368cc8d1f22493a9f2a9d7b5","datavalue":{"value":{"entity-type":"item","numeric-id":1588032,"id":"Q1588032"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1758159$644A9D23-85E4-4C5B-91B4-11A27028FC02","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"124bc1f07c83b194f9037b3e901637718270a57b","datavalue":{"value":{"entity-type":"item","numeric-id":5744696,"id":"Q5744696"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1758159$BDF077AF-06A5-4EAD-8DCD-8D4B45E474DE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"48933c0d362727730cc1905c68ff87e3a22216cf","datavalue":{"value":{"entity-type":"item","numeric-id":2457345,"id":"Q2457345"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1758159$AE84433D-FED5-4CDA-9AE1-B168824109A0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"477fad7e9eb44ad8a11dffc84ce40c6dfab6c50e","datavalue":{"value":{"entity-type":"item","numeric-id":1295781,"id":"Q1295781"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1758159$E72CBE8E-A47F-4D90-9A53-299D560300DE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"43a68a509eadf6111b0e06ec4b721711237d6038","datavalue":{"value":{"entity-type":"item","numeric-id":4660688,"id":"Q4660688"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1758159$BC784921-C68F-4E65-8A72-736155C319F6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a2ac0a8bea7b5fffcc0f153a7466174081cc680d","datavalue":{"value":{"entity-type":"item","numeric-id":5428110,"id":"Q5428110"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1758159$7B0EA2BC-E8F1-4CE7-A2CF-5B0474C5FCD9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"68b6d4fbabfa85170c6a6897ab0919170fbd0f9e","datavalue":{"value":{"entity-type":"item","numeric-id":2946515,"id":"Q2946515"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1758159$93A5B3FA-3B3F-42E7-8D60-53AF277617E3","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":"Q1758159$6CEE9D82-42FE-46A8-8FE5-5ED72938644C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8e64098d7a3f9ba0263d98df401722c77cb8e768","datavalue":{"value":{"entity-type":"item","numeric-id":4695386,"id":"Q4695386"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1758159$14906519-1CB0-4EA7-A18C-92F3E84EEBCF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ef00ea47cce625ccb5dfbb54f56161b7f25a74dd","datavalue":{"value":{"entity-type":"item","numeric-id":3753479,"id":"Q3753479"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1758159$3D0DDEF0-7AA0-4BE6-B45C-DACCE9FE3DBB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"50af3f972231f34c906a1f07770c69059b1c917d","datavalue":{"value":{"entity-type":"item","numeric-id":1770535,"id":"Q1770535"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1758159$DA498E73-0B7C-46D8-9B06-D58B69631632","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fad0073c05a86f235a75e5f7aa9afe4a3c7d1fb6","datavalue":{"value":{"entity-type":"item","numeric-id":819794,"id":"Q819794"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1758159$FFA76C9F-10E0-4E52-9BD1-E532DD052EF6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"95c7f3d983cb0969437a1008765e67c723c6449c","datavalue":{"value":{"entity-type":"item","numeric-id":5505187,"id":"Q5505187"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1758159$E3DFB46A-016B-438B-8B6F-445F2A4AC78B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8eeaa7dfd1d5aa46fe4ef30cb5d8e2f1a04648ae","datavalue":{"value":{"entity-type":"item","numeric-id":4507801,"id":"Q4507801"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1758159$E9652EA6-3E47-4144-B0A1-1F44C3286517","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e24f5eef2c31f4b3029541882abacbbb3a68ab4a","datavalue":{"value":{"entity-type":"item","numeric-id":5096173,"id":"Q5096173"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1758159$F2EC56D8-5929-425F-B422-9CA4D043A5BF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0983e33d87026b74eb0bc8ab2da66027d637f0e0","datavalue":{"value":{"entity-type":"item","numeric-id":4502650,"id":"Q4502650"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1758159$9A618E50-DA28-4CA6-BAEF-AFFB971B5B82","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"75ad48a62c35f967368f9ae540df4c4b7d918fdb","datavalue":{"value":{"entity-type":"item","numeric-id":5262772,"id":"Q5262772"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1758159$CB5BF930-0C05-475A-A782-B29F3F6A0B32","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"464af806ad669a8ba9fafa24982a3cac3c11e86f","datavalue":{"value":{"entity-type":"item","numeric-id":2378497,"id":"Q2378497"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1758159$55405927-3864-4BBF-A500-F15CA4DA8077","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bd34ef6d6fce4d6badff46e5860c71c69b26c8f7","datavalue":{"value":{"entity-type":"item","numeric-id":1361004,"id":"Q1361004"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1758159$517307A4-A757-4A9A-B652-F338F1B2DDD4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d50041fd827b9a880db5475227f379529c471731","datavalue":{"value":{"entity-type":"item","numeric-id":790612,"id":"Q790612"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1758159$8458AB16-D825-4EC1-BA8B-0B2F684DFF0E","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"fdcf5128e337d66a0da788de39bef0de279c7a30","datavalue":{"value":"10.1016/J.TCS.2012.08.002","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1758159$0E4972A1-B0E4-4534-819B-488A8F72B803","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5390c5403c5257037e4a67b0c864fc986ef8d6a2","datavalue":{"value":{"entity-type":"item","numeric-id":5254148,"id":"Q5254148"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2ac95a5c4fd2d7cc14e85f51538080f4470efe39","datavalue":{"value":{"amount":"+0.9495987296104432","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":"Q1758159$3BA4CEB2-B4DE-419F-B13A-77D3BA12038C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"54c83ccda9fca6a5043aee6cb8d5cefac3864b7b","datavalue":{"value":{"entity-type":"item","numeric-id":1361004,"id":"Q1361004"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4d5a2f51d48e60e1903f031cd4af83c7b713736e","datavalue":{"value":{"amount":"+0.8120430707931519","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":"Q1758159$9CB0DEDE-DE36-43BB-9772-30ADD19E56A3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f35068074d37ab08e13610b20505e002155d6beb","datavalue":{"value":{"entity-type":"item","numeric-id":1713027,"id":"Q1713027"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b0003ee8dd1f6c44bcf6fb8b67456a0335efeb64","datavalue":{"value":{"amount":"+0.7777056694030762","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":"Q1758159$67BCD55C-245E-4120-B2E3-788AD48C8103","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b17718e2684cd7221b6c5ff0aac7ec7526b87056","datavalue":{"value":{"entity-type":"item","numeric-id":1336772,"id":"Q1336772"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"61532c5db7a19f833338b9c51e82c34891c5a2da","datavalue":{"value":{"amount":"+0.7519674301147461","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":"Q1758159$4FB8A273-A47B-4388-9642-16CD02F0EF5D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"37a7c5b3d6c729b5afe89a3a8a3c8270958f403c","datavalue":{"value":{"entity-type":"item","numeric-id":3325832,"id":"Q3325832"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7ad7d4f23a0869551cad11252c6f0c979dbb1bd2","datavalue":{"value":{"amount":"+0.7278680205345154","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":"Q1758159$6EA54FD8-2363-4387-A667-BBE94F698B60","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1758159","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1758159"}}}}}