Time-Space Lower Bounds for NP-Hard Problems

University Of Wisconsin-Madison, Madison WI

Investigators

Abstract

This project studies the intrinsic power and limitations of current and future computing devices. The focus lies on so-called NP-complete problems, a ubiquitous class of computational problems and the subject of one of the seven millennium prize questions proposed by the Clay Mathematics Institute as grand challenges for the 21st century. No efficient algorithms for NP-complete problems are known. Such algorithms would have many applications in science and engineering but would also jeopardize the security of internet communication. In fact, all the cryptographic systems currently in use hinge on the assumption that there do not exist efficient algorithms for NP-complete problems. The goal of this research is to make progress in establishing that premise by showing that NP-complete problems do not have efficient algorithms that use a small amount of memory space. The investigator and other authors have shown that satisfiability does not have a deterministic algorithm that runs in time n^c and space n^d for certain nontrivial combinations of the constants c and d. The same holds for other natural NP-complete problems. This project intends to quantitatively improve the time-space lower bounds for NP-complete problems in the deterministic model. A concrete objective for satisfiability is a quadratic time lower bound for subpolynomial-space algorithms. The project also aims to establish similar lower bounds in the randomized and the quantum model, where currently nothing nontrivial is known. An ambitious long-term goal is to prove superpolynomial lower bounds for subpolynomial-space algorithms that solve more complex NP-hard problems like the permanent.