부분 결과원문 확인
Relational Queries Computable in Polynomial TimeNeil Immerman · 1986Information and Control 68(1–3), 86–104쪽 (1986) · 예비판 STOC 1982 (Proceedings of the 14th Annual ACM Symposium on Theory of Computing), 147–152쪽순서 있는 유한 구조에서, 1차 논리에 최소 고정점 연산자를 더한 논리로 적히는 성질이 곧 다항 시간에 판정되는 성질임을 보인 논문이다. Vardi 가 같은 정리를 독립적으로 얻었다(vardi-1982). Fagin 의 정리와 합치면 P = NP 를 논리의 표현력에 관한 문장으로 바꿔 적을 수 있다. 1-1 의 「여러 얼굴」 글이 인용한다. 저자 누리집의 공개본으로 연결한다.
확인:저자 공개본을 열어 정리 1 과 Vardi 의 독립 발견에 관한 서술을 읽음.원문 주소 (people.cs.umass.edu)이 카드를 붙인 자료 1