Open AccessLower bounds for the low hierarchy
Author(s) -
Eric Allender,
Lane A. Hemachandra
Publication year - 1989
Publication title -
lecture notes in computer science
Language(s) - English
Resource type - Book series
SCImago Journal Rank - 0.249
H-Index - 400
eISSN - 1611-3349
pISSN - 0302-9743
ISBN - 3-540-51371-X
DOI - 10.1007/bfb0035750
Subject(s) - hierarchy , computer science , analytical hierarchy , discrete mathematics , mathematics , theoretical computer science , combinatorics , analytic hierarchy process , mathematical economics , economics , market economy
The low hierarchy in NP [Sc-83] and the extended low hierarchy [BBS-86] have been useful in characterizing the complexity of certain interesting classes of sets. However, until now, there has been no way of judging whether or not a given lowness result is the best possible.
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom