Faster Algorithms for Computing All Prime Implicants of a Boolean Expression

The Hong Kong University of Science and Technology
Department of Computer Science and Engineering

Final Year Thesis Oral Defense

Title: "Faster Algorithms for Computing All Prime Implicants of a Boolean 
        Expression"

by

RUBAB Tamzid Morshed

Abstract:

A common problem in computer science is simplifying boolean functions: 
given a boolean function in some form e.g., Conjunctive Normal Form 
(C.N.F), we have to find the shortest equivalent expression (usually in 
Disjunctive Normal Form). Quine-McCluskey's algorithm does this by 
computing all prime implicants: an implicant of a boolean expression is a 
conjunct which implies the expression and it is prime implicant if no 
subset of this conjunct is an implicant of the expression. Thus in a sense 
prime implicants are the "shortest" conjuncts which imply the original 
expression. However, this algorithm takes exponential time as this problem 
is generally np-hard. Additionally, it assumes some structure about the 
input (e.g., all points where the expression is true has to be given). Our 
goal in this project is to design faster and parameterized algorithms to 
find all prime implicants of any given C.N.F expression.


Date            : 5 May 2023 (Friday)

Time            : 14:00 - 14:40

Venue           : Room 5562 (near lifts 27/28), HKUST

Advisor         : Dr. GOHARSHADY Amir

2nd Reader      : Prof. CHENG Siu-Wing