论文标题
分割的计算复杂性
Computational Complexity of Segmentation
论文作者
论文摘要
计算可行性是引导生物学和人工智能的框架和建模的广泛关注。认知系统能力的规范通常是由关于搜索空间和子分组复杂性的未直观的假设来塑造的。但是，错误的直觉可能会使这种最初的概念化误导了以后出现的经验问题。我们在这里进行了分割的计算级建模和复杂性分析 - 一个广泛假设的子分析，在跨领域的能力解释中起着必要的作用 - 作为一个案例研究，以表明正式评估这些假设的关键程度。我们从数学上证明了有关硬度和搜索空间大小的两组结果，这些结果可能与直觉相反，并将其含义与对亚能力的现有视图有关。
Computational feasibility is a widespread concern that guides the framing and modeling of biological and artificial intelligence. The specification of cognitive system capacities is often shaped by unexamined intuitive assumptions about the search space and complexity of a subcomputation. However, a mistaken intuition might make such initial conceptualizations misleading for what empirical questions appear relevant later on. We undertake here computational-level modeling and complexity analyses of segmentation - a widely hypothesized subcomputation that plays a requisite role in explanations of capacities across domains - as a case study to show how crucial it is to formally assess these assumptions. We mathematically prove two sets of results regarding hardness and search space size that may run counter to intuition, and position their implications with respect to existing views on the subcapacity.
