Computational complexity is a core theory of computer science, which dictates
the degree of difficulty of computation. There are many problems with high
complexity that we have to deal, which is especially true for AI. This raises a
big question: Is there a better way to deal with these highly complex problems
other than bounded by computational complexity? We believe that ideas and
methods from intelligence science can be applied to these problems and help us
to exceed computational complexity. In this paper, we try to clarify concepts,
and we propose definitions such as unparticularized computing, particularized
computing, computing agents, and dynamic search. We also propose and discuss a
framework, i.e., trial-and-error + dynamic search. Number Partition Problem is
a well-known NP-complete problem, and we use this problem as an example to
illustrate the ideas discussed.

本文旨在探讨计算机科学中的计算复杂性问题，提出了智能科学的思路和方法，运用试错和动态搜索的框架将 NP 完备问题 Number Partition Problem 作为案例进行讨论。

超越计算复杂度的试错动态行为与智能

Exceeding Computational Complexity Trial-and-Error Dynamic Action and Intelligence

A core interest in building Artificial Intelligence (AI) agents is to let
them interact with and assist humans. One example is Dynamic Search (DS), which
models the process that a human works with a search engine agent to accomplish
a complex and goal-oriented task. Early DS agents using Reinforcement Learning
(RL) have only achieved limited success for (1) their lack of direct control
over which documents to return and (2) the difficulty to recover from wrong
search trajectories. In this paper, we present a novel corpus-level end-to-end
exploration (CE3) method to address these issues. In our method, an entire text
corpus is compressed into a global low-dimensional representation, which
enables the agent to gain access to the full state and action spaces, including
the under-explored areas. We also propose a new form of retrieval function,
whose linear approximation allows end-to-end manipulation of documents.
Experiments on the Text REtrieval Conference (TREC) Dynamic Domain (DD) Track
show that CE3 outperforms the state-of-the-art DS systems.

探究利用 CE3 方法结合全文语料库压缩降维表示和线性函数检索提升动态搜索智能代理的文本检索效果。