폴리 로그 공간에 균일 한 RNC가 포함되어 있습니까? 공간 (때로는 PolyL로 작성 됨)에 포함됩니다.

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

RNCDSPACE(polylog)

RNC=NC

RNC

DSPACE(polylog)

NTIME(2polylog)

DTIME(2polylog)

Valentine Kabanets는 Russell Impagliazzo와의 논문에서 가 왜 가능성이 없는지를 설명하는 다음과 같은 (민속적인) 논증을 설명했습니다 .

RNCNTIME(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


답변