tovey.tutorial

Tutorial on Computational ComplexityCraig A. ToveySchoolofIndustrialandSystemsEngineering,GeorgiaInstituteofTechnology,Atlanta,Georgia30332ctovey@isye.gatech.eduThispaperwasrefereed.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 dis-crete 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 solutionmethod is appropriate. Complexity analysis helps you to understand and deal with hardproblems. It can pinpoint the nasty parts of your problem, alert you to a special structure youcan take advantage of, and guide you to model more effectively. You will solve your problembetter when you know the borders between hard and easy. Locating the difficulty canindicatewhere 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. Fixparameters of your problem to arrive at the known hard problem, or use specialization, pad-ding, forcing, or the more difficult gadget proofs. Study contrasting pairs of easy and hardproblems to develop your intuitive ability to assess complexity.(Analysisofalgorithms:computationalcomplexity.)omputational complexity is the measurement of assess complexity, I recommend this introduction andC ...