Log-space-uniform NC는 결정 성 폴리 로그 공간 (때로는 PolyL로 작성 됨)에 포함됩니다. log-space-uniform RNC가이 클래스에도 있습니까? PolyL의 표준 무작위 버전은 PolyL이어야하지만 (균일 한) RNC가 randomized-PolyL임을 알 수 없습니다.
제가보기 어려운 점은 RNC에서 회로가 원하는만큼 “임의의 비트를 볼”수 있다는 것입니다. 즉, 임의의 입력에 임의 팬 아웃이있을 수 있습니다. 그러나 임의 버전의 PolyL에서 원하는만큼 임의의 비트를 얻는 것과는 다릅니다. 오히려, 당신은 매 시간마다 동전을 뒤집을 수 있습니다.
감사!
답변
아마도 대부분의 사람들은 (또는 심지어 )라고 생각하지만 이것에 대해 회의적입니다 (두 번째 부분 참조) 내 답변, 아래). 경우 참에 포함 , 그 다음이 또한 포함된다 (더 구체적으로는 인 를 철저히 검색).R N C = N C R N C D S P A C E ( p o l y l o g ) N T I M E ( 2 p o l y l o g ) D T I
RNC⊆DSPACE(polylog)RNC=NC
RNC
DSPACE(polylog)
NTIME(2polylog)
DTIME(2polylog)
Valentine Kabanets는 Russell Impagliazzo와의 논문에서 가 왜 가능성이 없는지를 설명하는 다음과 같은 (민속적인) 논증을 설명했습니다 .
RNC⊆NTIME(2polylog)정리 : 만약 다음 중 N E X P는 크기의 부울 회로에 의해 계산 가능 아닌 O ( 2 N / N ) (즉, 서브 MAXSIZE하여 Shannon; 관련이 없지만 견고성에 대해서는 Lupanov 참조) 또는 Permanent는 준 다항식 크기의 Z 에 대한 (분할이없는) 산술 공식으로 계산할 수 없습니다 .
아르 자형엔기음⊆엔티나는엠이자형(2피영형엘와이엘영형지)엔이자형엑스피
영형(2엔/엔)
지
증명 : 가정 . Permanent에 준 다항식 크기 공식이있는 경우, 가정에 의해 준 다항식 시간 다항식 아이덴티티 테스터를 사용하여 Permanent에 대한 공식을 추측하고 확인할 수 있습니다. 이것은 N T I M E ( 2 p o l y l o g )에 Permanent를 배치 합니다.
아르 자형엔기음⊆엔티나는엠이자형(2피영형엘와이엘영형지)엔티나는엠이자형(2피영형엘와이엘영형지)
Toda의 정리에 의해 는 N T I M E ( 2 p o l y l o g )에도 있습니다. 패딩으로의 선형 지수 시간 버전 Σ 5 에서 또한 N E X P . 따라서 Σ 5 의 선형 지수 버전은 o ( 2 n / n ) 크기의 회로 를가집니다 (즉, submax). 그러나 간단한 대각선 화 인수로 선형 지수 버전 Σ 5
Σ2엔티나는엠이자형(2피영형엘와이엘영형지)
Σ5
엔이자형엑스피
Σ5
영형(2엔/엔)
Σ5
모순되는 최대 회로 크기가 필요합니다 (그런데, 이것은 대학원 수준의 복잡성 과정에 대한 중간 수준의 질문의 변형입니다. 아마, 에 최대 크기 회로가 필요 하다는 것을 증명할 수 있습니다. 더 간단한 것입니다). QED.
이자형엑스피에스피에이기음이자형
이제 인기가없는 방향입니다.
우리는 여러 번 읽은 임의성이 명백하지 않은 것을 할 수 있다는 것을 이미 알고 있습니다. 흥미로운 예는 Reinhardt and Allender의 ” 비결정론을 모호하지 않게 만들기 “에서 찾을 수 있습니다 (비 균일 성 측면에서 설명하지만 원칙적으로는 많은 시간에 임의성을 사용합니다). 또 다른 흥미로운 예는 (직접 관련이 적음) Emanuele Viola의 ” Randomness Buys Depth for Approximate Counting “입니다. 의 비 무작위 화가 대부분의 사람들이 기대하는 것이 아니라면 놀라지 않을 것이라고 생각합니다.
아르 자형엔기음(Noam Nisan의 1 회 읽기 대 많은 무작위성에 관한 멋진 논문과 같이, 한면의 오류로 양면 오류를 구입하는 방법을 보여주는 다른 논문도 있습니다.)
그건 그렇고, 입력에 대한 다중 액세스 (예 : 선형 길이 Bps)로 공간 제한 계산 모델을 속이는 PRG 구성 방법을 이해하는 것도이 질문과 관련이 있습니다.
-Periklis