Chennai Mathematical Institute

Seminars




11.00 am, Lecture Hall 1
M.Sc Thesis Defence
A Survey of Alternation-Trading Proofs for Time-Space Lower Bounds

Kumar Shubham
Chennai Mathematical Institute.
06-06-17


Abstract

Satisfiability has been one of the central problem to complexity theorist since its inception in 1971 in Cook's work on NP completeness. Though it has been widely believed to be intractable, no simultaneous linear time, logarithmic- space lower bound was known until recently. In 1997 Fortnow building on earlier work of Kannan, ruled out such an algorithm. Since then there has been notable progress with non-trivial lower bound. This talk will mention some of known lower bounds for time and space complexity of satisfiability on deterministic, nondeterministic model with random access and discuss how to achieve them. We conclude this article by extending Kannan's argument to address the power of nondeterministic log-space computation over unambiguous computation.