Hees, Arnaud van (2025) Interplay of Number Theory and Fixed-Parameter Tractable Algorithms. Bachelor's Thesis, Computing Science.
|
Text
bCS2025VanHeesA.pdf Download (512kB) | Preview |
|
![[img]](https://fse.studenttheses.ub.rug.nl/style/images/fileicons/text.png) |
Text
Toestemming.pdf Restricted to Registered users only Download (159kB) |
Abstract
This thesis investigates the fixed-parameter tractability of NP-hard number-theoretic problems. While parameterized complexity has been studied extensively in the field of graph theory, number theory has been comparatively underexplored. Motivated by bridging this gap, we study five NP-hard problems from Garey and Johnson’s 1979 book on ”Computer and Intractability”, each of which are related to core number-theoretic topics such as modular arithmetic, Diophantine equations, divisibility, and multiplication. The central research question guiding this thesis is ”What parameters are suitable for parameterization of NP-hard problems in number theory?” To answer this question, we explore a variety of parameterizations for each problem. These include bounds on solution variables, input sizes, and number-theoretic properties, such as the number of distinct prime factors appearing in parts of the input. Our contributions include nine fixed-parameter tractable (FPT) algorithms and one slice-wise polynomial (XP) algorithm. These algorithms leverage a variety of algorithmic techniques, including integer linear programming (ILP) with bounded constraints, dynamic programming over exponent vectors, brute-forcing over bounded search spaces, and classical number-theoretic techniques such as the Chinese Remainder Theorem (CRT) and Hensel’s Lemma. Overall, this thesis provides strong evidence for the relevance of parameterized complexity in number theory.
| Item Type: | Thesis (Bachelor's Thesis) |
|---|---|
| Supervisor name: | Bliznets, I. and Ramanayake, D.R.S. |
| Degree programme: | Computing Science |
| Thesis type: | Bachelor's Thesis |
| Language: | English |
| Date Deposited: | 10 Jul 2025 13:51 |
| Last Modified: | 15 Jul 2025 10:11 |
| URI: | https://fse.studenttheses.ub.rug.nl/id/eprint/35856 |
Actions (login required)
 |
View Item |