k-CNF SAT

k-CNF 충족 가능성 문제

절마다 리터럴이 최대 k개인 논리곱 표준형 논리식의 충족 가능성을 묻는 결정 문제로, k가 3 이상이면 NP-완전이다.

기사 1편최근 언급

k-CNF SAT(k-SAT)는 각 절(clause)에 리터럴이 최대 k개씩 들어 있는 논리곱 표준형(CNF) Boolean 논리식에 대해, 모든 절을 동시에 참으로 만드는 변수 값 배정이 있는지 묻는 결정 문제다. 충족 가능성 문제(SAT)의 특수한 경우로, 2-SAT는 다항 시간에 풀리지만 3-SAT를 비롯해 k가 3 이상이면 NP-완전이다.

SAT는 1971년 Stephen Cook이 NP-완전임을 증명한 최초의 문제이며, 3-SAT는 다른 문제의 NP-난해성을 보이는 환원의 출발점으로 널리 쓰인다. 변수가 n개일 때 모든 배정을 시험하면 2^n 시간이 들고, 2^{cn}(c<1) 시간에 동작하는 알고리즘들이 알려져 있다. 지수 시간 가설(ETH)은 이 문제를 준지수 시간에 풀 수 없다는 추측이다. 실무에서는 SAT 솔버가 하드웨어·소프트웨어 검증과 계획 문제 등에 쓰인다.

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

이 항목을 다룬 기사

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

    OpenAI가 공개한 논문 'The Exponential Time Hypothesis is False'의 핵심은 k-CNF 충족 가능성 문제를 준지수 시간, 정확히는 2^{o(n)} 시간에 푸는 결정적 알고리즘입니다.

    기사 읽기

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

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