Degree
Master of Science in Computer Science
Department
Department of Computer Science
School
School of Mathematics and Computer Science (SMCS)
Date of Submission
Summer 2022
Supervisor
Dr. Shahid Hussain, Associate Professor and Chairperson, Department of Computer Science
Committee Member 1
Dr. Jibran Rashid, Examiner – I,
Committee Member 2
Dr. Imran Rauf, Examiner – II
Abstract
Parameterized Complexity Theory aims to provide an expanded multivariate model of computational complexity. Similar to the classical theory, it contains many results on the structure of complexity classes. Most notably, we have the Weft Hierarchy of classes, which are believed to be situated in-between the parameterized version of P (known as FPT) and NP (known as para-NP). While the Weft Hierarchy is a structural refinement over the classical theory, many open problems remain in Parameterized Complexity Theory. Work needs to be done to refine our current understanding of the structural relationships between the parameterized classes and between parameterized and classical results. No up-to-date survey of literature has been published (since 2015) on this topic. We present a systematic way of searching for open problems in the field, using a deductive reasoning tool we have created for this purpose. Our tool includes visual ways of search and deduction. It is novel in the way it synthesizes the domain knowledge, and lets the researcher discover open problems.
Document Type
Restricted Access
Submission Type
Thesis
Recommended Citation
Zafar, Muhammad Abdullah. "A Deduction Tool for finding Open Problems in Parameterized Complexity Theory." Unpublished graduate research project. Institute of Business Administration. 2022. https://ir.iba.edu.pk/research-projects-mscs/29
The full text of this document is only accessible to authorized users.
