계산 복잡성

이 책은 복잡성 이론이 개념적 내용이 매우 풍부하다는 논문에 뿌리를 두고 있으며, 이 내용을 주제에 대한 설명과 강의에서 명확하게 전달해야 한다고 주장합니다. 해당 교과서 제공의 욕구가 현재 책을 쓰게 된 동기이자 주요 운영 원칙입니다. 이 책은 복잡성 이론에 대한 개념적 관점을 제공하며, 그 발표는 이 관점을 강조하도록 설계되었습니다. 주로 복잡성 이론을 배우고자 하는 학생들과 복잡성 이론에 대한 강의를 가르치고자 하는 교육자를 위해 작성되었습니다. 이 책은 또한 복잡성 이론에 대한 관심을 촉진하고 적절한 배경을 가진 일반 독자들도 접근할 수 있도록 하는 것을 목표로 하고 있습니다(이는 주로 추상적인 논의, 정의 및 증명에 편안한 것을 포함합니다). 우리는 대부분의 독자가 알고리즘에 대한 기본 지식을 가질 것으로 예상하거나, 적어도 알고리즘이라는 개념에 상당히 편안할 것이라고 생각합니다. 이 책은 복잡성 이론의 여러 하위 분야(예: 유사무작위성과 확률적 증명 시스템)를 다룹니다. 각 경우, 설명은 하위 분야에서 다루는 직관적인 질문에서 시작하며, 이것은 연구하는 개념에 구현됩니다. 설명은 이러한 질문의 기본 중요성, 이 질문과 개념의 실제 공식화에서 만든 선택, 답변의 기초가 되는 접근법, 그리고 이러한 답변에 내포된 아이디어를 논의합니다. 우리의 견해는 이러한 (-기술적") 측면이 이 분야의 핵심이며, 발표는 이 견해를 반영하려고 시도합니다.