{"id":765,"date":"2023-07-18T08:19:22","date_gmt":"2023-07-18T08:19:22","guid":{"rendered":"https:\/\/synasc.ro\/2023\/?page_id=765"},"modified":"2023-07-18T08:19:22","modified_gmt":"2023-07-18T08:19:22","slug":"so-the-problem-has-poor-complexity-what-next","status":"publish","type":"page","link":"https:\/\/synasc.ro\/2023\/so-the-problem-has-poor-complexity-what-next\/","title":{"rendered":"So the problem has poor complexity: what next?"},"content":{"rendered":"\n<h5 class=\"has-text-align-center wp-block-heading\"><strong>James Davenport<\/strong><\/h5>\n\n\n\n<h5 class=\"has-text-align-center wp-block-heading\"><strong>University of Bath, UK<\/strong><\/h5>\n\n\n\n<p class=\"has-text-align-center\"><strong>Abstract<\/strong><\/p>\n\n\n\n<p>Some interesting problems have a poor worst-case complexity, but may still be soluble in some, or many, cases. If appropriate, there is \u2018fixed-parameter tractability\u2019 as one way of describing the solubility. But in other cases, e.g. SAT-solving, there isn\u2019t necessarily a neat theoretical solution, but powerful practical ideas.<br>What can we say about problems around real quantifier elimination?<\/p>\n\n\n\n<p class=\"has-text-align-center\"><strong>Short bio<\/strong><\/p>\n\n\n\n<p>James Davenport did a PhD in computer algebra (integration) at Cambridge, then worked at IBM Research on what became Axiom. He also worked at Cambridge, Grenoble and Bath, and has been Hebron &amp; Medlock Professor of Information Technology at Bath since 1986. His Grenoble lecture notes contributed to \u201cCalcul Formel\u201d with Yvonne Siret and Evelyne Tournier, translated into English and Russian. He has been associated with SYNASC since 2019, and was awarded an Honorary Doctorate by UVT in 2019.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>James Davenport University of Bath, UK Abstract Some interesting problems have a poor worst-case complexity, but may still be soluble in some, or many, cases. If appropriate, there is \u2018fixed-parameter tractability\u2019 as one way of describing the solubility. But in other cases, e.g. SAT-solving, there isn\u2019t necessarily a neat theoretical solution, but powerful practical ideas.What [&hellip;]<\/p>\n","protected":false},"author":23,"featured_media":0,"parent":0,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-765","page","type-page","status-publish","hentry"],"_links":{"self":[{"href":"https:\/\/synasc.ro\/2023\/wp-json\/wp\/v2\/pages\/765","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/synasc.ro\/2023\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/synasc.ro\/2023\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/synasc.ro\/2023\/wp-json\/wp\/v2\/users\/23"}],"replies":[{"embeddable":true,"href":"https:\/\/synasc.ro\/2023\/wp-json\/wp\/v2\/comments?post=765"}],"version-history":[{"count":1,"href":"https:\/\/synasc.ro\/2023\/wp-json\/wp\/v2\/pages\/765\/revisions"}],"predecessor-version":[{"id":766,"href":"https:\/\/synasc.ro\/2023\/wp-json\/wp\/v2\/pages\/765\/revisions\/766"}],"wp:attachment":[{"href":"https:\/\/synasc.ro\/2023\/wp-json\/wp\/v2\/media?parent=765"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}