개관원문 확인
The New Complexity Landscape around Circuit MinimizationE. Allender · 2020Language and Automata Theory and Applications (LATA 2020), Lecture Notes in Computer Science, Springer, 3–16쪽최소 회로 크기 문제(MCSP)를 둘러싼 메타복잡도 연구의 최근 흐름을 정리한 개관이다. 「어떤 함수가 어렵다는 것을 증명하기가 왜 어려운가」라는 물음을 MCSP 의 복잡도 문제로 풀어 쓴다. 2-3 의 메타복잡도 글이 분야 소개와 MCSP 의 NP-완전성 증명이 어려운 까닭을 이 글에 기대어 적었다. 저자 누리집의 공개본으로 연결한다.
확인:저자 공개본을 열어 §2–§4 를 읽음.원문 주소 (people.cs.rutgers.edu)이 카드를 붙인 자료 1