HYPSVC.com
  1. P vs NP 문제 풀기
  2. 4. 부록
  3. 4-1 참고문헌 카드
  4. Nonrelativizing Separations
4-1

문헌 카드

이 문헌의 서지와, 이 카드를 붙인 자료입니다.

부분 결과서지만 확인
Nonrelativizing SeparationsH. Buhrman, L. Fortnow, T. Thierauf · 1998Proceedings of the 13th Annual IEEE Conference on Computational Complexity, 8–12쪽 (1998)

MA_EXP 에는 다항 크기 회로가 없음(MA_EXP ⊄ P/poly)을 보인 논문이다. 산술화와 대각선 논법을 결합해 상대화와 자연 증명 두 장벽을 함께 피한 회로 하한의 예로, 2-2 의 대수화 글이 인용한다.

확인:원문은 확인하지 못함. 서지는 DOI 등록 기록으로, 내용은 Aaronson–Wigderson 2009 §1.1 과 Aaronson 2017 정리 56 으로 확인.

이 카드를 붙인 자료 1