clarke@utcsri.UUCP (06/04/87)
THEORY SEMINAR, Thursday, June 11, 3 pm, GB120
(GB = Galbraith Building, 35 St. George Street)
Professor Lane A. Hemachandra
Cornell University
``THE SKY IS FALLING:
The Strong Exponential Hierarchy Collapses"
The polynomial hierarchy plays a dominant role in classifying the complex-
ity of feasible computations. Composed of the levels P, NP, NP(NP) ,
etc., the grand obsession of complexity theory is to discover whether these
levels collapse. This goal is reflected in our romantic fixation on the
P=NP question. Love, devotion, and NSF grants notwithstanding, the ques-
tion of the the collapse of the polynomial hierarchy continues to defy
solution, and may lie beyond the scope of current mathematical proof tech-
niques.
We resolve the question of collapse for an exponential analogue of the
polynomial hierarchy. Composed of the levels E, NE, NP(NE), etc., the
strong exponential hierarchy collapses to P(NE): P(NE)=NP(NE)! Our proof
stresses the use of partial census information and the extraordinary
exploitation of nondeterminism.
We survey recent related results in structural complexity that also
spotlight counting.
--
Jim Clarke -- Dept. of Computer Science, Univ. of Toronto, Canada M5S 1A4
(416) 978-4058
{allegra,cornell,decvax,linus,utzoo}!utcsri!clarke