提出多项式时间可学习的布尔函数生成框架，揭示其与经典学习理论的关系。
Polynomial-Time Mistake-Bounded Language Generation
- 在多项式时间内实现误判有界的语言生成，基于布尔函数家族的结构特性
- 发现对称函数、2CNF、单调函数等家族可多项式时间学习，且误判数有界
- 证明该框架不闭合于并集，且存在可多项式学习但不可误判有界的情况
本文提出了 Kleinberg、Peale 与 Reingold（2026）提出的误判有界语言生成（MBLG）框架的多项式时间版本。我们对若干简单布尔函数族给出了上下界：首先，变量奇偶性、对称函数和2CNF是多项式时间MBLG；其次，具有多项式多极小项的单调函数也是多项式时间MBLG，例如仅含一个极大项的字面析取式即属于此类。在强RSA假设下，我们证明字面析取式并非多项式时间MBLG，由此推出多项式时间MBLG族不闭合于并集，且存在多项式时间 PAC 可学习但非多项式时间 MBLG 的函数族。最后，在单向注入函数存在的假设下，我们构造出多项式时间 MBLG 但不可多项式时间 PAC 学习的函数族。
原文摘要 · Abstract (English)
In this paper, we introduce a polynomial-time version of the mistake-bounded language generation (MBLG) framework due to Kleinberg, Peale, and Reingold (2026). We obtain upper and lower bounds for a number of simple families of Boolean functions. Namely, we first observe that families of parities of variables, symmetric functions and 2CNFs are polynomial-time MBLG. We then show that the family of monotone functions with polynomially-many maxterms is polynomial-time MBLG. For instance, disjunctions of literals are monotone Boolean functions with 1 maxterms, and thus polynomial-time MBLG. Under the strong RSA assumption, we show that disjunctions of literals are not polynomial-time MBLG. From the latter result, we deduce that polynomial-time MBLG families are not closed under union, and that there are families that are polynomial-time PAC learnable but not polynomial-time MBLG (again, under the strong RSA assumption). Finally, assuming existence of injective one-way functions, we show that there are polynomial-time MBLG families that are not polynomial-time PAC learnable.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。