HYPSVC.com
  1. P vs NP 문제 풀기
  2. 4. 부록
  3. 4-1 참고문헌 카드
  4. The Permanent Requires Large Uniform Threshold Circuits
4-1

문헌 카드

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

부분 결과서지만 확인
The Permanent Requires Large Uniform Threshold CircuitsEric Allender · 1999Chicago Journal of Theoretical Computer Science, Volume 1999, Article 7 (1999년 8월 6일 게재)

퍼머넌트는 크기 T(n) 인 균일한 상수 깊이 문턱 회로로 계산할 수 없음을 보인 논문이다 — T 는 몇 번 거듭 합성해도 2^n 보다 느리게 자라는 임의의 함수다. PP 나 #P 에 대해 어려운 모든 문제에 같은 하한이 적용된다. 균일성 조건이 붙은 하한이라서 비균일 TC⁰ 하한과는 다르다는 점에 주의해 인용한다. 「균일 회로에 대해서는 무엇이 증명되어 있는가」를 다루는 글에 필요하다.

확인:DOI 가 넘겨 주는 학술지 누리집의 논문 페이지(http://cjtcs.cs.uchicago.edu/articles/1999/7/contents.html)에서 제목·저자·권·논문 번호·게재일과 초록을 확인했다(Crossref 등록 기록에는 제목이 비어 있다).

이 카드를 붙인 자료 0

아직 이 카드를 붙인 자료가 없습니다.