Tutorial on Computational Complexity

Craig A. Tovey ()
Additional contact information
Craig A. Tovey: School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, Georgia 30332

Interfaces, 2002, vol. 32, issue 3, 30-61

Abstract: Computational complexity measures how much work is required to solve different problems. It provides a useful classification tool for OR/MS practitioners, especially when tackling discrete deterministic problems. Use it to tell, in advance, whether a problem is easy or hard. Knowing this won't solve your problem, but it will help you to decide what kind of solution method is appropriate. Complexity analysis helps you to understand and deal with hard problems. It can pinpoint the nasty parts of your problem, alert you to a special structure you can take advantage of, and guide you to model more effectively. You will solve your problem better when you know the borders between hard and easy. Locating the difficulty can indicate where to aggregate, decompose, or simplify. To detect and prove computational difficulty, show that a known hard problem from the literature is embedded within your problem. Fix parameters of your problem to arrive at the known hard problem, or use specialization, padding, forcing, or the more difficult gadget proofs. Study contrasting pairs of easy and hard problems to develop your intuitive ability to assess complexity.

Keywords: Analysis; of; algorithms:; computational; complexity (search for similar items in EconPapers)
Date: 2002
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (7)

Downloads: (external link)
http://dx.doi.org/10.1287/inte.32.3.30.39 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orinte:v:32:y:2002:i:3:p:30-61

Access Statistics for this article

More articles in Interfaces from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().