{"id":15114,"date":"2022-06-18T19:29:25","date_gmt":"2022-06-18T23:29:25","guid":{"rendered":"https:\/\/carleton.ca\/scs\/?page_id=15114"},"modified":"2026-06-08T14:53:27","modified_gmt":"2026-06-08T18:53:27","slug":"tr-232-on-the-complexity-of-computing-grobner-bases-in-characteristic-2","status":"publish","type":"page","link":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1993\/tr-232-on-the-complexity-of-computing-grobner-bases-in-characteristic-2\/","title":{"rendered":"TR-232: On the Complexity of Computing Gr\u00f6bner Bases in Characteristic 2"},"content":{"rendered":"\n<section class=\"w-screen px-6 cu-section cu-section--white ml-offset-center md:px-8 lg:px-14\">\n    <div class=\"space-y-6 cu-max-w-child-5xl  md:space-y-10 cu-prose-first-last\">\n\n            <div class=\"cu-textmedia flex flex-col lg:flex-row mx-auto gap-6 md:gap-10 my-6 md:my-12 first:mt-0 max-w-5xl\">\n        <div class=\"justify-start cu-textmedia-content cu-prose-first-last\" style=\"flex: 0 0 100%;\">\n            <header class=\"font-light prose-xl cu-pageheader md:prose-2xl cu-component-updated cu-prose-first-last\">\n                                    <h1 class=\"cu-prose-first-last font-semibold !mt-2 mb-4 md:mb-6 relative after:absolute after:h-px after:bottom-0 after:bg-cu-red after:left-px text-3xl md:text-4xl lg:text-5xl lg:leading-[3.5rem] pb-5 after:w-10 text-cu-black-700 not-prose\">\n                        TR-232: On the Complexity of Computing Gr\u00f6bner Bases in Characteristic 2\n                    <\/h1>\n                \n                                \n                            <\/header>\n\n                    <\/div>\n\n            <\/div>\n\n    <\/div>\n<\/section>\n\n\n\n<p>Carleton University<br><a href=\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1993\/\">Technical Report<\/a>&nbsp;<strong>TR-232<\/strong><br>December 1993<\/p>\n\n\n\n<h2 id=\"on-the-complexity-of-computing-grobner-bases-in-characteristic-2\" class=\"wp-block-heading\">On the Complexity of Computing Gr\u00f6bner Bases in Characteristic 2<\/h2>\n\n\n\n<p>Vincenzo Acciaro<\/p>\n\n\n\n<h3 id=\"abstract\" class=\"wp-block-heading\">Abstract<\/h3>\n\n\n\n<p>The computation of a Grobner basis over a field F is characterized by a space complexity which grows doubly exponentially with the number of variables. Existing proofs of this fact use nonelementary results from commutative algebra and algebraic geometry. In this paper we use an elementary argument to show that, when char(F) = 2, and the number of variables is unbounded, the problem of computing a Grabner basis is NP-hard.<\/p>\n\n\n\n<p><a href=\"https:\/\/carleton.ca\/scs\/wp-content\/uploads\/sites\/260\/TR-232.pdf\">TR-232.pdf<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Carleton UniversityTechnical Report&nbsp;TR-232December 1993 On the Complexity of Computing Gr\u00f6bner Bases in Characteristic 2 Vincenzo Acciaro Abstract The computation of a Grobner basis over a field F is characterized by a space complexity which grows doubly exponentially with the number of variables. Existing proofs of this fact use nonelementary results from commutative algebra and algebraic [&hellip;]<\/p>\n","protected":false},"author":2,"featured_media":0,"parent":11912,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"_acf_changed":false,"_cu_dining_location_slug":"","footnotes":"","_links_to":"","_links_to_target":""},"cu_page_type":[],"class_list":["post-15114","page","type-page","status-publish","hentry"],"acf":{"cu_post_thumbnail":""},"_links":{"self":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/15114","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/comments?post=15114"}],"version-history":[{"count":2,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/15114\/revisions"}],"predecessor-version":[{"id":24441,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/15114\/revisions\/24441"}],"up":[{"embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/11912"}],"wp:attachment":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/media?parent=15114"}],"wp:term":[{"taxonomy":"cu_page_type","embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/cu_page_type?post=15114"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}