Complexity Classes in Optimization | SpringerLink
Skip to main content
Springer Nature Link
Log in

Complexity Classes in Optimization

  • Reference work entry
Encyclopedia of Optimization

  • 470 Accesses

Article Outline

Keywords

Time and Space Complexity of Turing Machines

Definition of the Complexity Classes

  General Comments

Efficient Reducibility and ‘Hard’ Problems

See also

References

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 365365
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Hardcover Book
JPY 331617
Price includes VAT (Japan)
  • Durable hardcover edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

References

  1. Aho AV, Hopcroft JE, Ullman JD (1974) The design and analysis of computer algorithms. Addison-Wesley, Reading, MA

    MATH  Google Scholar 

  2. Arnon DS, Buchberger B (1988) Algorithms in real algebraic geometry. Acad. Press, New York

    MATH  Google Scholar 

  3. Arora S, Lund C, Motwani R, Sudan M, Szegedy M (1992) Proof verification and hardness of approximation problems. Proc 33rd IEEE Symp Foundations of Computer Sci., pp 14–23

    Google Scholar 

  4. Book RV (1974) Comparing complexity classes. JCCS 9:213–229

    MATH  MathSciNet  Google Scholar 

  5. Borosh I, Treybig LB (1976) Bounds on positive integral solutions of linear Diophantine equations. In: Proc Amer Math Soc, vol 55, pp 294–304

    Google Scholar 

  6. Canny J (1988) Some algebraic and geometric computations in PSPACE. Proc. 20th Annual ACM Symposium on Theory of Computing, 460–467

    Google Scholar 

  7. Cobham A (1964) The intrinsic computational difficulty of functions. In: Bar-Hillel Y (ed) Proc. 1964 Internat. Congress for Logic, Methodology and Philosophy of Sci. North-Holland, Amsterdam, 24–30

    Google Scholar 

  8. Cook SA (1971) The complexity of theorem-proving procedures, Proc. Third ACM Symp. Theory of Computing, pp 151–158

    Google Scholar 

  9. Davis M (1958) Computability and unsolvability. McGraw-Hill, New York

    MATH  Google Scholar 

  10. Edmonds J (1965) Paths, trees, and flowers. Canad J Math 17:449–467

    MATH  MathSciNet  Google Scholar 

  11. Elgot CC, Robinson A (1964) Random access stored program machines. J ACM 11:365–399

    Article  MATH  MathSciNet  Google Scholar 

  12. Garey MR, Johnson DS (1979) Computers and intractability. A guide to the theory of NP-completeness. Freeman, New York

    MATH  Google Scholar 

  13. Hartmanis J, Hunt III HB (1974) The LBA problem and its importance in the theory of computing. Complexity of Computation 1–26

    Google Scholar 

  14. Hartmanis J, Lewis PM, Stearns RE (1965) Classification of computations by time and memory requirements. Proc. IFIP Congress, 31–35

    Google Scholar 

  15. Hartmanis J, Stearns RE (1965) On the computational complexity of algorithms. Trans Amer Math Soc 117:285–306

    Article  MATH  MathSciNet  Google Scholar 

  16. Hochbaum DS (1979) Approximation algorithm for NP-hard problems. PWS, Boston, MA

    Google Scholar 

  17. Hopcroft JE, Ullman JD (1969) Formal languages and their relation to automata. Addison-Wesley, Reading, MA

    MATH  Google Scholar 

  18. Karp RM (1972) Reducibility among combinatorial problems. In: Miller RE, Thatcher JW (eds) Complexity of Computer Computations. Plenum, New York, pp 85–103

    Google Scholar 

  19. Khachian LG (1979) A polynomial algorithm for linear IV programming. Soviet Math Dokl 20, 191–194. (Dokl Akad Nauk USSR 224 (1979), 1093–1096)

    Google Scholar 

  20. Lengauer T, Wagner KW (1992) The correlation between the complexities of non-hierarchical and hierarchical versions of graph problems. JCSS 44:63–93

    MATH  MathSciNet  Google Scholar 

  21. Marathe MV, Hunt III HB, Rosenkrantz DJ, Stearns RE (1998) Theory of periodically specified problems: complexity and approximability. Proc. 13th IEEE Conf. Computational Complexity

    Google Scholar 

  22. Marathe MV, Hunt III HB, Stearns RE, Radhakrishnan V (1997) Complexity of hierarchically and 1-dimensional periodically specified problems I: hardness results. In: Du D-Z, Gu J, Pardalos PM (eds), Satisfiability Problem Theory and Appl. DIMACS 35. Amer. Math. Soc., pp 225–259

    Google Scholar 

  23. Matijasevic YV (1970) Enumerable sets are Diophantine, Soviet Math Dokl 11:354–357 (Dokl Akad Nauk USSR 191 (1970), 279–282)

    Google Scholar 

  24. Meyer AR, Stockmeyer LJ (1972) The equivalence problem for regular expressions with squaring requires exponential times. Proc. 13th Annual Symposium on Switching and Automata Theory, pp 125–129

    Google Scholar 

  25. Nemhauser GL, Wolsey LA (1988) Integer and combinatorial optimization. Interscience Ser Discrete Math and Optim. Wiley, New York

    MATH  Google Scholar 

  26. Orlin JB (1984) Some problems on dynamic/periodic graphs. Program. Combin. Optim. Acad. Press, New York, pp 273–293

    Google Scholar 

  27. Orlin JB (1985 1978) The complexity of dynamic/periodic languages and optimization problems. Sloan WP, vol 1676-86. MIT, Cambridge, MA. A preliminary version of this paper appears in Proc. 13th annual ACM Symposium on Theory of Computing, 1978, pp 218–227

    Google Scholar 

  28. Padalos PM (1993) Complexity in numerical optimization. World Sci., Singapore

    Google Scholar 

  29. Papadimitriou CH (1994) Computational complexity. Addison-Wesley, Reading, MA

    MATH  Google Scholar 

  30. Papadimitriou CH, Steiglitz K (1982) Combinatorial optimization: Algorithms and complexity. Prentice-Hall, Englewood Cliffs, NJ

    MATH  Google Scholar 

  31. Papadimitriou CH, Yannakakis M (1991) Optimization, approximation, and complexity classes. JCCS 43:425–440

    MATH  MathSciNet  Google Scholar 

  32. Sahni S (1974) Computationally related problems. SIAM J Comput 3:262–279

    Article  MathSciNet  Google Scholar 

  33. Savitch WJ (1970) Relationship between nondeterministic and deterministic tape complexities. JCSS 4:177–192

    MATH  MathSciNet  Google Scholar 

  34. Seiferas JJ, Fischer MJ, Meyer AR (1973) Refinements of nondeterministic time and space hierarchies, Proc. 14th Annual IEEE Symp. Switching and Automata Theory, pp 130–137

    Google Scholar 

  35. Sheperdson JC, Sturgis HE (1963) Computability of recursive functions. JACM 10:217–255

    Article  Google Scholar 

  36. Turing AM (1936/7) On computable numbers, with an application to the Entscheidungsproblem. Proc London Math Soc (2) 49:230–265

    Google Scholar 

  37. Vavasis SA (1991) Nonlinear optimization: Complexity issues. Oxford Sci. Publ., Oxford

    MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. University Albany, New York, USA

    H. B. Hunt III

Authors
  1. H. B. Hunt III
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Department of Chemical Engineering, Princeton University, Princeton, NJ, 08544-5263, USA

    Christodoulos A. Floudas

  2. Center for Applied Optimization, Department of Industrial and Systems Engineering, University of Florida, Gainesville, FL, 32611-6595, USA

    Panos M. Pardalos

Rights and permissions

Reprints and permissions

Copyright information

© 2008 Springer-Verlag

About this entry

Cite this entry

Hunt III, H.B. (2008). Complexity Classes in Optimization . In: Floudas, C., Pardalos, P. (eds) Encyclopedia of Optimization. Springer, Boston, MA. https://doi.org/10.1007/978-0-387-74759-0_76

Download citation

Publish with us

Policies and ethics

Search

Navigation