Russell Impagliazzo

러셀 임팔리아조

지수 시간 가설을 제안하고 '다섯 세계' 분류로 알려진 University of California, San Diego의 미국 컴퓨터과학자다.

기사 1편최근 언급

Russell Impagliazzo는 미국의 이론 컴퓨터과학자로, University of California, San Diego 컴퓨터과학과 교수다. University of California, Berkeley에서 Manuel Blum의 지도로 박사 학위를 받았으며 계산 복잡도 이론, 암호학, 의사 난수성(pseudorandomness)을 연구한다.

Ramamohan Paturi와 함께 k-SAT의 복잡도를 연구하며 지수 시간 가설(ETH)을 제안했다. 1995년에는 P 대 NP 문제와 암호학의 관계에 따라 가능한 세계를 Algorithmica, Heuristica, Pessiland, Minicrypt, Cryptomania의 다섯 가지로 나눈 '다섯 세계' 논의로 널리 알려졌다. 의사 난수 생성기와 탈무작위화에 관한 Impagliazzo–Wigderson 정리에도 이름이 붙어 있다.

이 설명은 AIPOST 기사와 널리 알려진 사실을 바탕으로 정리했습니다. 잘못된 내용이 있으면 정정 요청으로 알려 주세요.

이 항목을 다룬 기사

  • OpenAI의 AI가 ETH 반증, P 대 NP와 암호 체계는 어떻게 되나AI 뉴스 ·

    약 30년 전 Russell Impagliazzo, Ramamohan Paturi, Francis Zane이 제안했고, 이후 수백 편의 논문이 이 가설을 참으로 전제하고 쓰였습니다.

    기사 읽기

설명이 잘못되었거나 찾는 항목이 없나요?

위키 설명은 AIPOST 기사와 널리 알려진 사실을 바탕으로 정리합니다. 잘못된 설명은 정정 요청으로 알려 주시면 확인해 고칩니다. 새 기사에 나온 이름은 기사가 올라온 뒤 위키에 더해집니다.