Seminar: Scaled-down Rice's Theorem And Connections With Satisfiability Problem

Shadab Romani
M.Sc. Thesis Proposal
Supervisor: Dr. Antonina Kolokolova & Dr. Miklos Bartha

Scaled-down Rice's Theorem And Connections With Satisfiability Problem

Department of Computer Science
Thursday, January 28, 2016, 1:40 p.m., Room EN 2022


Abstract

Scaled-down Rice's theorem is a conjecture about the hardness of deciding semantic properties of Boolean circuits. According to this conjecture, having access to succinct description of a circuit does not give any significant computational advantage compared to pure oracle access when we want to
decide a property that only depends on the input-output behaviour of circuit. We investigate what implications the scaled-down Rice's theorem being true or false have for satisfiability problem. Additionally, we analyse variants of this conjecture by restricting its original statement to computationally limited sub-classes of general Boolean circuits.

 

Contact

Department of Computer Science

230 Elizabeth Ave, St. John's, NL, CANADA, A1B 3X9

Postal Address: P.O. Box 4200, St. John's, NL, CANADA, A1C 5S7

Tel: (709) 864-8000