두 글자가 같지 않도록 Σ 위에있는 모든 k 문자 문자열 로 구성된 언어 L k – d i s t i n c t를 고려하십시오 .
L k – d i s t i n c t : = { w = σ 1 σ 2 . . . σ k ∣ ∀ i ∈ [ k ] : σ i ∈ Σ 및 ∀ j ≠ i : σ j ≠ σ i }
이 언어는 유한하며 규칙적입니다. 특히 | Σ | = n
이 언어를 받아들이는 가장 작은 비 결정적 유한 오토 마톤은 무엇입니까?
현재 다음과 같은 느슨한 상한과 하한이 있습니다.
-
구성 할 수있는 가장 작은 NFA는 4 k ( 1 + o ( 1 ) ) ⋅ p o l y l o g ( n )
4k(1+o(1))⋅polylog(n) 상태입니다. -
다음의 정리는 2 K
2k 상태의 하한을 의미합니다 .
하자 L ⊆ Σ ∗
L⊆Σ∗ 일반 언어합니다. i = j 인 경우에만 x_i \ cdot w_j \ in L 이되도록 엔n 쌍 P = { ( x i , w i ) ∣ 1 ≤ i ≤ n }P={(xi,wi)∣1≤i≤n} 있다고 가정 합니다. 그런 다음 L을 수락하는 NFA는 적어도 n 개의 상태를 갖습니다.xi⋅wj∈Lxi⋅wj∈L i=ji=j
- 또 다른 (사소한) 하한은 log
log (nk)(nk) . 이는 언어에 대한 가장 작은 DFA 크기의 로그입니다.
I는 (에만 고정 부분을 수용하는 NFA 쌍이에 관심 0<ϵ<1
편집 : 나는 텍스트에 실수가있는 현상금을 시작했습니다.
k = O (log (n))을 쓰는 동안 k = polylog (n) 이라고 가정 할 수 있었습니다 .k=polylog(n)
편집 2 :
바운티가 곧 종료 될 것이므로 누구나 쉽게 얻을 수있는 방법에 관심이 있다면 다음 언어를 고려하십시오.
L(r,k)−distinct:={w:w
(예 : L(1,k)−distinct=Lk−distinct
주석의 구성과 유사한 구조는 대해 크기의 오토 마톤을 제공합니다. .O(ek⋅2k⋅log(1+r)⋅poly(n))
이것을 개선 할 수 있습니까? 이 언어에 가장 적합한 하한은 무엇입니까?
답변
이것은 대답이 아니라 개선 된 하한으로 떠날 것이라고 믿는 방법입니다. 후 우리가 문제를 잘라 보자 문자를 읽을 수 있습니다. 가족 나타낸다 의 요소 세트 [ N ] 에 의해 및 패밀리 B = K를 - 의 요소 세트 [ N ] 에 의해 B . 요소 읽은 후에 도달 될 수있는 상태를 의미 함으로써 (임의의 순서로) S 요소 읽은 후 수용성 상태에 도달 할 수있는 상기 상태 B 가 (임의의 순서로)를 T B
이 문제는 본질적으로 선 그래프가 (부분적으로) 알려진 하이퍼 그래프의 정점 수에 대한 하한을 요구합니다. 유사한 문제들이 예를 들어 Bollobas 에 의해 연구되었으며 유용 할 수있는 몇 가지 알려진 증명 방법이 있습니다.
업데이트 2014년 3월 24일은 : 사실 위의 하이퍼 그래프는에 실현 될 수있는 경우 의 정점, 우리는 또한 길이의 비 결정적 통신 복잡한 프로토콜을 얻을 로그 의 크기의 입력 세트와 세트 disjointness에 대한 와 B (사실 두 가지 문제를 동일합니다). 병목 현상은 물론 a = b = k / 2 일 때 Eyal 및 Noam의 책에서만 다음을 찾을 수 있습니다 .N 1 ( D I S J a ) ≤ log ( 2 k log e (
답변
진행중인 일부 작업 :
하한을 4 k 증명하려고합니다 . 여기에 그런 하한을 줄 것이라고 확신하는 질문 이 있습니다. 함수 f 가 존재 하도록 최소 t를 찾으십시오 . : { S ⊆ [ n ] , | S | = k / 2 } → { 0 , 1 } t 불연속성 을 유지, 즉 S 1 ∩ S 2 = ∅ iff f ( S 1 ) ∩ f (
나는이 질문에 대한 해결책이 의사 소통 복잡성 문헌 (특히 불연속성 문제를 다루는 논문에서, 아마도 일부 매트릭스 순위 인수가 도움이 될 것임)이나 인코딩에 관한 문헌 (예 : 이와 같은 ) 에서 이미 알려져 있다고 생각한다 .