Assistant Professor, Ph.D.
Department of Computer and Information Sciences
113 W 60th St., New York NY 10023
The most immediate objective of the conducted research is the development of the new and efficient method for the exact solution for the Minimum Disjunctive Normal Form (MDNF) problem. The research on the new method for the generation of prime implicants, which has already been completed, was the first and necessary step for finding a solution for the MDNF problem. The research on the solution for the MDNF problem has been, to some extent, conducted simultaneously with the research on the new method for the generation of prime implicants. This has been possible because the problem of prime implicants generation is considered to be an intrinsic part of the solution for the MDNF problem. The research on the solution for the MDNF problem is already advanced in the sense that the methodology, notation, proof techniques, as well as the simulation programs, have already been developed. There exist also some conjectures as to what algorithms for the MDNF problem would constitute a solution. What remains is to refine the conjectured solution, and to provide the correctness proof of the proposed approach. In case of the successful completion of the immediate research goal, i.e. the solution for the MDNF problem, the research would be carried out even further. The next goals would include extensions of the proposed approach to Boolean functions in various other representations and to multiple-output Boolean functions, and application of the research on Boolean functions to problems in graph theory. The possible successful extension of the research to problems in graph theory is indicated by the already established close relation of the proposed method to the solution for the CLIQUE problem in boolean graphs.
T. Strzemecki (1992). "Polynomial-Time Algorithms for Generation of Prime Implicants", Journal of Complexity, 8(1):37-63 http://links-ms.typeset.io/prod/a3562bcb-b6d1-42d9-9163-525b21c573e6/4595a9c6-7e89-434c-bf2f-3dd96c8f74fe
T. Strzemecki (1993). "A Linear Upper Bound on the Number of Prime Implicants", International Symposium for Young Computer Scientists, Beijing, China, July, 1993.
T. Strzemecki (1991). "Construction of Small-Depth Circuits", Proceedings of the International Conference for Young Computer Scientists, 312-316, Beijing, China, July, 1991.
X. Li, T. Strzemecki, B. Fang, and T. Qin (1989). "A New Result for an Old Problem - How Many Prime Implicants Are There in a Boolean Function?", Proceedings of Beijing International Symposium for Young Computer Proffesionals, 616-619, August, 1989.