부분 결과서지만 확인
Generalized First-Order Spectra and Polynomial-Time Recognizable SetsRonald Fagin · 1974R. M. Karp (ed.), Complexity of Computation, SIAM–AMS Proceedings 7, American Mathematical Society, 43–73쪽 (1974)유한 구조의 성질이 NP 에 속하는 것과 존재 2차 논리의 식으로 적히는 것이 같음을 보인 논문이다. 기계도 시간도 쓰지 않고 NP 를 논리의 표현력으로 특징지은 Fagin 의 정리의 원전이다. 1-1 의 「여러 얼굴」 글이 인용한다. 논문 본문을 열지 못해, 정리를 소개하는 위키백과 문서로 연결한다.
확인:논문 본문은 열지 못함. 서지는 Immerman 1986 의 참고문헌과 위키백과 「Fagin's theorem」 문서로, 정리의 진술은 Immerman 1995 의 정리 1 로 확인.원문 주소 (en.wikipedia.org)이 카드를 붙인 자료 1