본 논문은 Grohe와 Turán이 제시한 논리적 프레임워크 내에서 관계형 배경 구조에 대한 부울 분류 문제를 연구합니다. 다항 로그 정도의 구조에서 일차 논리로 정의 가능한 분류기는 하위 선형 시간 내에 학습될 수 있다는 사실이 알려져 있습니다(Grohe and Ritzert, LICS 2017). 본 논문은 Kuske와 Schweikardt(LICS 2017)가 다양한 다른 계수 논리를 일반화하는 표현력 있는 논리로 소개한 일차 논리 계수 FOCN으로 결과를 일반화합니다. 구체적으로, 다항 로그 정도의 구조 클래스에 대해 FOCN으로 정의 가능한 분류기는 일관되게 하위 선형 시간 내에 학습될 수 있음을 증명합니다. 이는 기계 학습의 수치적 측면을 포함하도록 학습 프레임워크를 확장하는 첫 번째 단계로 볼 수 있습니다. 또한, 어떤 상수 c에 대해 최대 $(\log \log n)^c$ 정도의 구조 클래스에 대한 불확정적 PAC 학습으로 결과를 확장합니다. 더욱이, 하위 선형 시간 학습 알고리즘을 얻기 위해서는 정도를 제한하는 것이 중요함을 보여줍니다. 즉, 정도가 제한되지 않은 구조의 경우, 일반적인 일차 논리로 정의 가능한 분류기에 대해서도 하위 선형 시간 내에 학습이 불가능함을 증명합니다.
