AI-완전

3. AI-완전 문제의 예시

다음은 AI-완전 문제로 가설이 세워진 문제들이다.

• AI 동료 검토^[12] (복합적인 자연어 이해, 자동 추론, 자동 정리 증명, 형식화된 논리 전문가 시스템)
• 봉가드 문제^[13]
• 컴퓨터 비전 (및 객체 인식과 같은 하위 문제)^[14]
• 자연어 이해 (및 텍스트 마이닝^[15], 기계 번역^[16], 단어 의미 중의성 해소^[17]와 같은 하위 문제)
• 자율 주행^[18]
• 내비게이션, 계획 또는 전문가 시스템이 수행하는 종류의 추론과 같이 실제 세계의 문제를 해결하는 동안 예상치 못한 상황에 대처하는 것

4. 공식화

계산 복잡도 이론은 계산 가능 함수의 상대적인 계산 난이도를 다룬다. 정의상, 해결책이 알려지지 않았거나 공식적으로 특성화되지 않은 문제는 다루지 않는다. 많은 AI 문제들이 아직 공식화되지 않았기 때문에, 기존의 복잡도 이론으로는 AI-완전성을 공식적으로 정의할 수 없다.

5. 연구

로만 얌폴스키^[20]는 문제 $C$가 AI 문제 집합(인간 오라클로 해결 가능)에 속하고, 어떤 AI 문제든 다항 시간 알고리즘으로 $C$로 변환될 수 있다면 '''AI-완전'''하다고 제안했다. 문제 $H$가 '''AI-어렵다'''는 것은 AI-완전 문제 $C$가 $H$로 다항 시간 튜링 환원될 수 있을 때만 해당된다. 이는 '''AI-쉽다''' 문제의 존재를 낳는다. 얌폴스키^[21]는 튜링 테스트가 AI-완전성의 정의적 특징이라고 가설을 세웠다.

그로페와 자인^[22]은 인공 일반 지능이 필요한 문제를 AI-완전 문제로 분류했지만, 현재 AI 시스템으로는 제한된 버전만 해결할 수 있다고 보았다. 셰크르스트^[23]는 계산 복잡성 연구 부족이 인공 일반 지능 달성을 제한한다고 강조했다. 크위-빈토로와 벨레즈^[24]는 AI-완전 문제 해결이 사회에 강력한 영향을 미칠 것이라고 보았다.

5. 1. 얌폴스키의 제안

• AI 문제 집합(인간 오라클로 해결 가능)에 속한다.
• 어떤 AI 문제든 다항 시간 알고리즘으로 $C$로 변환될 수 있다.

5. 2. 기타 연구

• AI 문제 집합(인간 오라클로 해결 가능)에 속한다.
• 어떤 AI 문제든 다항 시간 알고리즘으로 $C$로 변환될 수 있다.

6. 한국의 AI-완전 연구 동향

(이전 출력이 비어있으므로, 수정할 내용이 없습니다. 원본 소스와 요약 정보가 제공되면 다시 시도해주세요.)

참조

_[1] 간행물 Artificial Intelligence http://www.cse.buffa[...] 1992
_[2] 논문 Turing Test as a Defining Feature of AI-Completeness http://cecs.louisvil[...] 2013-01
_[3] 간행물 CAPTCHA: Using Hard AI Problems for Security http://www.captcha.n[...] 2003
_[4] 논문 Natural Language Steganography and an "AI-complete" Security Primitive 2006-01-07
_[5] 간행물 The 1988 Annual Meeting of the International Studies Association. http://citeseer.ist.[...] 2007-04-27
_[6] 간행물 Daydreaming and Computation http://ftp.cs.ucla.e[...] 1987-03
_[7] 간행물 Jargon File Version 2.8.1 http://catb.org/esr/[...] 1991-03-22
_[8] 서적 Building Large Knowledge-Based Systems Addison-Wesley
_[9] 웹사이트 A Generalist Agent https://www.deepmind[...] 2022-05-26
_[10] 간행물 Welcome to the Era of the AI Coworker {{!}} Backchannel https://www.wired.co[...] 2024-04-28
_[11] 웹사이트 Unveiling the Power of Large Language Models (LLMs) https://www.unite.ai[...] 2024-04-28
_[12] 간행물 If AI Can Fix Peer Review in Science, AI Can Do Anything https://www.wired.co[...] 2024-04-27
_[13] 간행물 AI-Completeness: Using Deep Learning to Eliminate the Human Factor https://doi.org/10.1[...] Springer International Publishing 2024-03-25
_[14] 논문 Vision and robotics 2020
_[15] 서적 Proceedings of the 45th International ACM SIGIR Conference on Research and Development in Information Retrieval ACM 2023-04-15
_[16] 간행물 Say It Right: AI Neural Machine Translation Empowers New Speakers to Revitalize Lemko https://link.springe[...] Springer International Publishing 2023-04-15
_[17] 논문 Introduction to the special issue on word sense disambiguation: the state of the art https://www.aclweb.o[...]
_[18] 인터뷰 Elon Musk talks Twitter, Tesla and how his brain works — live at TED2022 https://www.youtube.[...] 2022-12-15
_[19] 간행물 Guide to Deep Learning Basics https://philarchive.[...] Springer 2020
_[20] 간행물 AI-Complete, AI-Hard, or AI-Easy – Classification of Problems in AI https://www.proceedi[...] 2024-04-05
_[21] 간행물 Turing Test as a Defining Feature of AI-Completeness 2013
_[22] 논문 The Way Forward with AI-Complete Problems 2024
_[23] 간행물 AI-Completeness: Using Deep Learning to Eliminate the Human Factor https://doi.org/10.1[...] Springer International Publishing 2024-04-05
_[24] 간행물 AI-Complete: What it Means to Be Human in an Increasingly Computerized World Springer 2022