Art

J-GLOBAL ID：201602207370319414   Reference number：16A0052389

Exploring the Limits of Subadditive Approaches: Parallels between Optimization and Complexity Theory

劣加法的アプローチの限界を探る:最適化と複雑性理論の類似点

Author (1)： UENO Kenya (The Hakubi Center for Advanced Res. and Graduate School of Informatics, Kyoto Univ.)
Material： Interdisciplinary Information Sciences  (Interdiscip Inf Sci)
Volume： 21  Issue： 4  Page： 329-349 (J-STAGE)  Publication year： 2015 
JST Material Number： L2559A  ISSN： 1340-9050  Document type： Article
Article type： 原著論文  Country of issue： Japan (JPN)  Language： ENGLISH (EN)

Thesaurus term： *optimization ,  mathematical programming ,  *computational complexity ,  *formula ,  limit ,  integer programming ,  proof(evidence)
Semi thesaurus term： lower bound ,  *computational complexity ,  *logic formula

JST classification (1)： Applied mathematics  (AB11000P)

Reference (47)：

• 1) A. Ambainis. Polynomial degree vs. quantum query complexity. Journal of Computer and System Sciences, 72(2):220-238, 2006.
• 2) E. Balas, S. Ceria, and G. Cornuéjols. A lift-and-project cutting plane algorithm for mixed 0-1 programs. Mathematical Programming, 58:295-324, 1993.
• 3) J. Balcázar, J. Díaz, and J. Gabarró. Structural Complexity I, 2nd edition. Springer, 1994.
• 4) D. A. Barrington. Bounded-width polynomial-size branching programs recognize exactly those languages in NC¹. Journal of Computer and System Sciences, 38(1):150-164, 1989.
• 5) E. Böhler, N. Creignou, S. Reith, and H. Vollmer. Playing with Boolean blocks, part I: Post's lattice with applications to complexity theory. ACM SIGACT News, 34(4):38-52, 2003.

Terms in the title (6)： 加法 ,  限界 ,  最適化 ,  複雑性 ,  理論 ,  類似