회선값 문제
Circuit Value Problem
회로 값 문제(또는 회로 평가 문제)는 특정 입력에 대한 특정 부울 회로의 출력을 계산하는 계산 문제입니다.
균일한0 AC저감 하에서의 P에 대한 문제는 완전히 해결되었습니다.시간 복잡성의 관점에서, 이것은 단순히 위상 정렬에 의해 선형 시간 내에 해결될 수 있습니다.
부울 수식 값 문제(또는 부울 수식 평가 문제)는 회선이 트리인 경우의 특수한 경우입니다.NC의1 [1]Boolean 공식 값 문제가 완료되었습니다.
이 문제는 NP에 대해 완료된 부울 만족도 문제와 co-NP에 대해 완료된 명제 동질성 문제와 밀접하게 관련되어 있습니다.
레퍼런스
- ^ Buss, Samuel R. (January 1987). "The Boolean formula value problem is in ALOGTIME". www.math.ucsd.edu. Retrieved May 5, 2017.
