내가 실제로 이해하지 못한다는 것을 항상 알고 있었던 한 가지 차이점은 회로 복잡성이 비 균일 버전을 나타내고 튜링 머신은 일이 균일 한 비 균일과 균일 한 계산 복잡성 사이입니다. “uniform”은 n + 1 변수의 문제와 비교하여 n 변수의 문제에 대해 완전히 다른 회로를 허용하지 않는 알고리즘 클래스를 제한하는 방법이라고 생각합니다.
내 질문은 : 1) 회로 측면에서 균일성에 대한 설명이 있으며, 2) 훨씬 더 강력한 형태의 균일 성이 제공되어 효과적인 (또는 제한 된) 알고리즘에 대한 제한적인 개념을 제공 할 수 있습니까? P는?
늦은 설명 : 2 번 문제는 “실제적으로”다항식 알고리즘의 클래스와 같은 힘을 갖는 제한된 알고리즘 클래스에 관한 것입니다.
답변
첫 번째 질문에 대한 답은 부정적이라고 생각합니다. 회로에는 고정 된 수의 입력이 있으므로 IMO는 하나의 균일 한 회로가 아닌 회로의 “가족”에 대해서만 이야기 할 수 있습니다.
두 번째 질문과 관련하여 튜링 머신에 의해 생성 된 “균일 한 회로 제품군”이있을 수 있습니다. 즉, 균일 한 회로 군으로하고 M을 튜링 기계로 하자 . 다음에, 각 N , [ C N ] = M ( 1 N ) 여기서, [ C n은 ] 의 설명이다 C , N을 .
{Cn}M
n
[Cn]=M(1n)
[Cn]
Cn
균일 한 회로 제품군으로 정의 된 P 아래에 몇 가지 복잡성 클래스가 있습니다. 예를 들면 다음과 같습니다.
결정 문제의 클래스가있다 decidable균일게이트와 깊이의 다항식 수가 부울 회로O( 로그 I를 N).
NCiO(login)
답변
위의 Sadeq의 대답에 덧붙여 P에 포함 된 회로 클래스를 볼 때 점점 더 제한적인 균일 성 개념을보고 싶을 수도 있습니다.
가장 간단하고 가장 잘 알려진 개념은 P- 균일 성인데, 이는 시간 poly (n)에서 회로 을 생성하는 (결정 론적) Turing Machine M이 있어야한다는 요구 사항입니다 (Suresh talks). 보다 제한적인 균일 성 버전은 M의 검정력을 더 제한하려고합니다. 예를 들어, M이 공간 O (log (n))에서 실행되어야하는 Logspace-uniformity도 있습니다.
Cn내가 아는 가장 제한적인 개념은 작은 회로 클래스에 사용되는 DLOGTIME-uniformity입니다. 여기서, (현재 랜덤 액세스) 머신 (M)은 단지 시간 O (log n)를 가지므로 전체 회로의 설명을 기록 할 수 없다. 부과 된 조건은 i와 n이 주어지면 M은 회로 설명의 i 번째 비트를 시간 O (log n)로 기록 할 수 있다는 것입니다.
자세한 내용은 다음 논문을 참조하십시오. David A. Mix Barrington, Neil Immerman, Howard Straubing : NC¹ 내의 균일 성. J. 컴퓨팅 시스. 공상 과학 41 (3) : 274-306 (1990).
답변
회로와 균일 한 계산을 “통합”하는 한 가지 방법은 을 취해 조언 회로 C n을 출력 하는 복잡성 제한 절차를 요구하는 것 입니다. P의 경우 위의 작업을 수행 할 수있는 다항식 생성기가 필요하면 P를 올바르게 캡처 할 수 있다고 생각합니다.
nCn
답변
회로 측면에서 균일성에 대한 설명이 있습니까?
1
f(|x|)
f
FO
DLogTime
AC0
FO
여기서 요점은 회로의 균일 성을 정의하기 위해 일정한 계산 모델이 필요하다는 것입니다. 회로에 대한 설명이 균일하지 않은 수단으로 제공되면 회로가 불균일 할 수 있습니다.
답변
1) 회로 측면에서 균일성에 대한 설명이 있습니까?
[이것은 Dick Lipton의 블로그에서 요청한 것과 동일한 질문에 대한 내 답변의 편집 된 버전입니다. 주의 사항 : 저는 전문가가 아닙니다.]
적어도 두 가지 종류의 예라고 생각합니다.
a) 회로는 문제 입력 크기에서 다항식 시간으로 튜링 머신에 의해 생성 될 수 있습니다 (다른 응답에서 언급 한 바와 같이). (이것이 개념의 표준 정의라고 생각합니다.)
여기에는 균일하게 호출 할 수있는 회로 제품군이 포함되지만 P- 시간 개념의 정의로 회로 제품군에 대한 정의를 Turing 머신의 정의로 줄입니다.
b) 문제 해결을 위해 문제 입력으로 진화하는 1 차원 셀룰러 오토 마톤이있는 경우 (결정 문제의 경우, 솔루션은 입력을 포함하는 셀에 대해 지정된 셀에서 단일 비트이며, 이는 안정적인 상태 임) 입력 크기의 다항식 시간에서, 이것은 간단한 방식으로 2D로 주기적이며 (시간 단위당 셀당 하나의 반복 단위), 2 차적으로 큰 영역에서만 문제가되는 회로에 해당합니다. 솔루션 시간에.
이것은 매우 특별한 종류의 균일 회로 제품군이지만 튜링 머신은 1D CA로 쉽게 인코딩 할 수 있기 때문에 P의 모든 문제를 해결하기에 충분합니다. (이것은 또한 이전 회신에서 언급 된 DLOGTIME- 균일 성의 정의를 만족시키는 것으로 보입니다.)
(이것은 Lipton의 블로그에서 Gowers의 답변에 언급 된 회로로 Turing 머신의 인코딩과 유사합니다. 실제로는 그 중 하나가 동일 할 것입니다.)
튜링 머신을 1D CA로 인코딩하는 한 가지 방법 : 각 셀에서 테이프 포인트 상태를 한 지점에서 나타내고 튜링 머신 헤드가 현재 상태 인 경우 상태를 나타냅니다 (없는 경우 값이 중요하지 않음). , 그리고 머리가 여기 있는지 여부를 말하는 약간의 비트. 분명히, 시각 t에서의 그러한 각각의 상태는 시각 t-1에서의 바로 인접한 이웃 상태에만 의존하며, 이것이 CA로서 작용하기 위해 필요한 전부이다.