HYPSVC.com
  1. P vs NP 문제 풀기
  2. 4. 부록
  3. 4-1 참고문헌 카드
  4. A Better-Than-3n Lower Bound for the Circuit Complexity of an Explicit Function
4-1

문헌 카드

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

부분 결과서지만 확인
A Better-Than-3n Lower Bound for the Circuit Complexity of an Explicit FunctionM. G. Find, A. Golovnev, E. A. Hirsch, A. S. Kulikov · 2016FOCS 2016 (57th Annual IEEE Symposium on Foundations of Computer Science), 89–98쪽 · ECCC TR15-166 (2015)

구체적인 함수에 대한 일반 회로 하한을 (3 + 1/86)n − o(n) 으로 올린 논문이다. Blum 의 3n 기록을 30여 년 만에 넘어섰지만 여전히 선형 수준이다. 2-3 의 회로 하한 글이 인용한다. ECCC 공개본으로 연결한다.

확인:ECCC TR15-166 의 초록까지 확인. 본문을 읽었다는 기록은 없음.
원문 주소 (eccc.weizmann.ac.il)이 카드를 붙인 자료 1

이 카드를 붙인 자료 1