As early as the late 1800’s, scientists in Russia wrote about classes of mathematics problems that appeared to require “Perebor” (brute-force search) techniques for their solution. In spite of the fact that we can often prove existence of certain truths, we’re no closer to practically solving these problems today e.g. certain kinds of secret codes are known to be breakable no matter that it can take hundreds of thousands of years of compute power to find the key. These problems are especially well known. For example the Clay Institute offers a $1,000,000 prize for anyone that can prove whether or not it’s possible for these problems to be solved efficiently. But of course, that’s just for fun. The security of world financial transactions, military based communications, missile launches, your iPhone, and even your front door keyless combination lock depends upon these truths.
Dr. Steve Gismondi works with students and collaborators to study these problems and their solutions. This is the field of classical and quantum complexity theory. In particular, his interests are focused upon studying heuristic solution techniques applied to NP and coNP-complete decision problems.
A decision problem is classified as belonging to NP if a correctly guessed decision can be verified in polynomial time e.g. “Is graph G Hamiltonian?”. The complementary problem is classified as belonging to coNP e.g. “Is G non-Hamiltonian?”. Some decision problems belong to both NP and coNP, and some decision problems are commonly solved in polynomial time e.g. “Is an LP feasible?”. In recent work, Dr. Gismondi study coNP by searching for subsets of instances of coNP-complete decision problems for which correctly guessed decisions can be verified in polynomial time.
