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.
翻译:计算可行性是指导生物和人造情报的制定和建模的广泛关注,认知系统能力的具体要求往往受到关于搜索空间和次比较复杂性的未经审查的直觉假设的左右,然而,错误的直觉可能使这种初始概念错误地导致对后来实际问题的相关性产生误解。我们在这里进行分化的计算层面建模和复杂分析,这种分析在解释跨领域能力方面起必要作用的广度虚构的次计算,作为案例研究,表明正式评估这些假设有多重要。我们从数学上证明了两组关于硬性和搜索空间大小的结果,这些结果可能与直觉相悖,并表明其对子能力的现有观点的影响。