CC(복잡성)
CC (complexity)계산 복잡성 이론에서 CC(Comparator Circuits)는 다항식 크기의 비교기 회로에 의해 해결될 수 있는 의사결정 문제를 포함하는 복잡성 등급이다.
대조군 회로는 각 대조군 게이트가 지시되고, 각 와이어가 입력 변수, 그 부정 또는 상수로 초기화되며, 와이어 중 하나가 출력 와이어로 구분되는 정렬 네트워크다.
CC에게 완성되는 가장 중요한 문제는 안정된 결혼 문제의 결정 변종이다.
정의
비교기 회로는 와이어와 게이트의 네트워크다.두 와이어를 연결하는 방향 에지인 각 대조군 게이트는 두 개의 입력을 취하여 정렬된 순서로 출력한다(가장 큰 값이 에지가 가리키는 와이어에 도달하는 값).어떤 와이어에 대한 입력은 변수, 그 부정 또는 상수가 될 수 있다.와이어 중 하나가 출력 와이어로 지정되어 있다.회로가 계산한 기능은 입력 변수에 따라 와이어를 초기화하여 비교기 게이트를 순서대로 실행하고 출력 와이어가 전달하는 값을 출력하여 평가한다.
비교기 회로 값 문제(CCVP)는 회로와 회로에 대한 입력의 인코딩이 주어진 비교기 회로를 평가하는 문제다.복잡도 등급 CC는 로그공간을 CCVP로 축소할 수 있는 문제 등급으로 정의된다.[1]등가 정의는[2] AC로0 CCVP로 환원 가능한 문제의 등급이다.
예를 들어, 분류 네트워크를 사용하여 중간선을 출력 와이어로 지정하여 다수 계산에 사용할 수 있다.
중간 와이어가 출력으로 지정되고 와이어에 16개의 다른 입력 변수로 주석을 달면 결과 비교기 회로가 대부분을 계산한다.AC에서0 구성할 수 있는 정렬 네트워크가 있기 때문에, 이것은 대다수의 기능이 CC에 있음을 보여준다.
CC 완료 문제
CC의 문제는 로그 공간 축소를 사용하여 CC의 모든 문제를 줄일 수 있다면 CC-완전이다.비교기 회로 값 문제(CCVP)는 CC-완전이다.
안정된 결혼 문제에는 남녀가 동등하게 존재한다.한 사람 한 사람이 이성의 모든 구성원의 순위를 매긴다.현재 파트너보다 서로를 선호하는 비장애인이 없다면 남녀 매칭은 안정적이다.안정적인 매칭은 항상 존재한다.안정된 매치 중에서, 각각의 여성이 어떤 안정된 매칭에서든 가장 좋은 남자를 얻는 것이 있다; 이것은 여성-최적 매칭으로 알려져 있다.안정적 매칭 문제의 결정판은 모든 남녀의 순위를 고려할 때, 주어진 남자와 주어진 여자가 여자-최적 매칭에서 일치하는지 여부다.고전적인 게일-샤플리 알고리즘은 대조군 회로로 구현할 수 없지만, 수브라마니안은[3] 문제가 CC에 있다는 것을 보여주는 다른 알고리즘을 고안해 냈다.문제는 역시 CC-완전이다.
CC-완전한 또 다른 문제는 사전 편찬적-최초 일치다.[3]이 문제에서, 우리는 정점에 순서가 있는 초당적 그래프와 가장자리가 주어진다.사전 통계학적으로 첫 번째 최대 일치점은 첫 번째 양분에서 두 번째 양분에서 사용 가능한 최소 정점까지 연속적으로 정점을 일치시켜 얻는다.문제는 주어진 에지가 이 일치에 속하는지 묻는다.
스콧 애런슨은 조약돌 모델이 CC-완전하다는 것을 보여주었다.[4]이 문제에서 시작 숫자의 조약돌과 두 가지 유형의 지시만 포함할 수 있는 프로그램에 대한 설명이 제공되며, 두 가지 유형의 지침만 포함될 수 있다 크기 {\와 의 새 크기더미를 얻거나 y }의 더미를 분할한다.을(를) 크기 더미 / ⌉ \\ \ \ y/2\rceil 과) { {{ { { {{ { . \ \ \ \ \ \ \ \ \ \. 문제는 프로그램을 실행한 후 특정 더미에 조약돌이 존재하는지 결정하는 것이다그는 이것을 디지-콤프 II와 같은 장치에서 볼이 지정된 싱크 정점에 도달하는지 여부를 결정하는 문제도 CC-완전하다는 것을 보여주기 위해 사용했다.
밀폐합물
비교기 회로 평가 문제는 다항식 시간 내에 해결할 수 있으므로, CC는 P("회로 보편성")에 포함되어 있다.반면에 비교기 회로는 방향 도달성을 해결할 수 있으므로 CC는 NL을 포함한다.[3]CC와 NC가 비교할 수 없을 만큼 상대적인 세계가 있어 두 가지 모두 엄밀하다.[2]
참조
- ^ E. W. Mayr; A. Subramanian (1992). "The complexity of circuit value and network stability". Journal of Computer and System Sciences. 44 (2): 302–323. doi:10.1016/0022-0000(92)90024-d.
- ^ a b S. A. Cook; Y. Filmus; D. T. M. Le (2012). "The complexity of the comparator circuit value problem". arXiv:1208.2721.
- ^ a b c A. Subramanian (1994). "A new approach to stable matching problems". SIAM Journal on Computing. 23 (4): 671–700. doi:10.1137/s0097539789169483.
- ^ Aaronson, Scott (4 July 2014). "The Power of the Digi-Comp II". Shtetl-Optimized. Retrieved 28 July 2014.
