English

运筹学学报

• 运筹学 • 上一篇    下一篇

离散优化与连续优化的复杂性概念

邢文训1,*   

  1. 1. 清华大学数学科学系, 北京 100084
  • 收稿日期:2017-04-04 出版日期:2017-06-15 发布日期:2017-06-15
  • 通讯作者: 邢文训 E-mail: wxing@math.tsinghua.edu.cn
  • 基金资助:

    国家自然科学基金(No. 11571029)

Complexity concepts for combinatorial and continuous optimization problems

XING Wenxun1,*   

  1. 1. Department of Mathematical Sciences, Tsinghua University, Beijing 100084, China
  • Received:2017-04-04 Online:2017-06-15 Published:2017-06-15

PDF

612

被引次数

1

摘要：

问题的复杂性概念起源于离散的图灵计算机理论的研究, 在离散优化问题的研究中被广泛的接受. 近期连续优化领域的很多文章中提及NP难这个概念. 从而来对比介绍离散优化和连续优化研究中这两个概念的差异.

关键词: 复杂性概念, 离散优化, 连续优化

Abstract:

 Complexity concepts oriented from the theoretical Turing machine are widely accepted in study of combinatorial optimization problems. The polynomially computable and NP-hard concepts are frequently used in recent papers on continuous optimization problems. This paper presents a very brief introduction to show their relationship and difference used in the two fields.

Key words: complexity concepts, combinatorial optimization, continuous optimization