판정 문제
위키백과 ― 우리 모두의 백과사전.
계산 가능성 이론과 계산 복잡도 이론에서 판정 문제란 어떤 형식 체계에서 예-아니오 답이 있는 질문을 말한다. 결정 문제라고도 한다. 예를 들어 "두 숫자 x와 y가 있을 때 y는 x로 나누어 떨어지는가?" 하는 질문이 있다. 답은 x와 y 값에 따라 '예' 또는 '아니오' 중 하나가 될 수 있다.
판정 문제를 푸는 데 쓰인 방법을 알고리즘이라고 한다. 어떤 판정 문제를 푸는 알고리즘이 있으면 그 문제는 판정 가능하다고 한다. 없으면 판정 불가능하다고 한다.
| 이 문서는 토막글입니다. 서로의 지식을 모아 알차게 문서를 완성해 갑시다. |

