# Report

## Dominance: consistently comparing computational complexity

Abstract:

Though complexity theory strives primarily to categorize problems according to their complexity, it is typically the complexity only of methods of solving problems that we can directly measure. Specifically, we have an upper bound for a problem's complexity: namely, the complexity of the most efficient known solution method for the problem. In order to improve such bounds, it is desired to consider sets of solution methods that are as complete as possible; but, whilst comparisons of computing...

Publication status:
Published
Peer review status:
Not peer reviewed

### Access Document

Files:
• (Version of record, pdf, 180.6KB)

### Authors

More by this author
Institution:
University of Oxford
Division:
MPLS
Department:
Computer Science
Oxford college:
Queen's College
Role:
Author
Publisher:
Oxford University Computing Laboratory Publisher's website
Publication date:
2008-01-01
Language:
English
Keywords:
Subjects:
UUID:
Local pid:
ora:4907
Deposit date:
2011-02-09