Complexity of Operators on Compact Sets

被引：4
作者：
Zhao, Xishun [1 ]
Mueller, Norbert [2 ]
机构：
[1] Sun Yat Sen Univ, Inst Log & Cognit, Guangzhou 510275, Guangdong, Peoples R China
[2] Univ Trier, FB 04, Abt Informat, D-54286 Trier, Germany
来源：
ELECTRONIC NOTES IN THEORETICAL COMPUTER SCIENCE | 2008年 / 202卷
关键词：
Oracle Turing machines; compact sets; operator complexity; projection; convex hull;
D O I：
10.1016/j.entcs.2008.03.011
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
Based on oracle Turing machines, we investigate the computational complexity of operators on compact sets. For the projection and convex hull we are able to show exponential upper and lower bounds as well as a connection to the P=NP problem for special settings.
引用
收藏
页码：101 / 119
页数：19
相关论文
共 50 条
  • [31] Efficient computation of the convex hull on sets of points stored in a k-tree compact data structure
    Felipe Castro, Juan
    Romero, Miguel
    Gutierrez, Gilberto
    Caniupan, Monica
    Quijada-Fuentes, Carlos
    KNOWLEDGE AND INFORMATION SYSTEMS, 2020, 62 (10) : 4091 - 4111
  • [32] Approximation by harmonic functions in the Cm-norm and harmonic Cm-capacity of compact sets in Rn
    Gorokhov, YA
    MATHEMATICAL NOTES, 1997, 62 (3-4) : 314 - 322
  • [33] Efficient computation of the convex hull on sets of points stored in a k-tree compact data structure
    Juan Felipe Castro
    Miguel Romero
    Gilberto Gutiérrez
    Mónica Caniupán
    Carlos Quijada-Fuentes
    Knowledge and Information Systems, 2020, 62 : 4091 - 4111
  • [34] Approximating sets on a plane with optimal sets of circles
    P. D. Lebedev
    A. V. Ushakov
    Automation and Remote Control, 2012, 73 : 485 - 493
  • [35] THE COMPLEXITY OF PHONOLOGY
    Kornai, Andras
    Sichel, Ivy
    LINGUISTIC INQUIRY, 2009, 40 (04) : 701 - 723
  • [36] Explicit convex hull description of bivariate quadratic sets with indicator variables
    De Rosa, Antonio
    Khajavirad, Aida
    MATHEMATICAL PROGRAMMING, 2024,
  • [37] Typical convex sets
    E. M. Bronshteîn
    Siberian Mathematical Journal, 2000, 41 : 13 - 18
  • [38] APPROXIMATELY CONVEX SETS
    Huynh, Van Ngai
    Penot, Jean-Paul
    JOURNAL OF NONLINEAR AND CONVEX ANALYSIS, 2007, 8 (03) : 337 - 355
  • [39] On parallel sum of operators
    Tian, Xiaoyi
    Wang, Shuaijie
    Deng, Chunyuan
    LINEAR ALGEBRA AND ITS APPLICATIONS, 2020, 603 : 57 - 83
  • [40] On decomposability of Multilinear sets
    Alberto Del Pia
    Aida Khajavirad
    Mathematical Programming, 2018, 170 : 387 - 415
12345