스파스어

계산 복잡성 이론에서 희박한 언어는 언어의 길이 n 문자열 수를 세는 복잡함수가 n의 다항 함수에 의해 경계되는 형식 언어(현악 집합)이다.그것들은 주로 다른 등급과의 복잡도 등급 NP의 관계에 대한 연구에 사용된다.모든 희박한 언어의 복잡성 클래스를 스파스라고 부른다.

희소언어는 총 2개의ⁿ 길이 n의 현이 있기 때문에 희소언어라고 불리는데, 어떤 언어가 다항적으로 이 중 많은 문자열만을 포함하고 있다면, n이 커짐에 따라 그 언어가 포함하는 길이 n의 문자열의 비율은 빠르게 0으로 간다.모든 단일한 언어는 희박하다.비종교 희소 언어의 예로는 일부 고정 k에 대해 정확히 k 1비트를 포함하는 이진 문자열 집합이 있다$.{\displaystyle }$ 각 n에는 n으로^k 경계되는 (${\displaystyle \genfrac{}{}{0ex}{}{n}{}}$ k${\displaystyle }$) ${\$개의 문자열만$$ 있다.

다른 복잡성 클래스와의 관계

SPRASS에는 단일 언어의 클래스인 TALIGE가 포함되어 있는데, 이는 단일 언어의 문자열이 한 길이에 불과하기 때문이다.P/poly의 모든 언어가 희박한 것은 아니지만, P/poly의 어떤 언어에서 희박한 언어로의 다항 시간 튜링 감소가 있다.^[1]1979년 포춘은 어떤 희박한 언어가 공동 NP-완전하다면 P = NP;^[2] 마하니는 1982년에 이것을 이용하여 만약 희박한 언어가 NP-완전하다면 P = NP(이것이 마하니의 정리)라는 것을 보여주었다.^[3]이를 증명할 수 있는 보다 간단한 왼쪽 세트에 근거한 증거는 1991년 오기하라와 와타나베에 의해 제시되었다.^[4]Mahaney의 주장은 실제로 희박한 언어를 NP로 요구하지 않기 때문에 P = NP인 경우에만 희박한 NP-하드 집합이 있다.^[5]또한, P에 없는 NP에 희박한 언어가 존재하는 경우에만 E ≠ NE.^[6]There is a Turing reduction (as opposed to the Karp reduction from Mahaney's theorem) from an NP-complete language to a sparse language if and only if ${\displaystyle {\textbf {NP}}\subseteq {\textbf {P}}/{\text{poly}}}$. In 1999, Jin-Yi Cai and D.오기하라가 작업 중인 시바쿠마르는 희박한 P-완전 문제가 존재한다면 L = P라는 것을 보여주었다.^[7]

참조

외부 링크

• 랜스 포트나우가장 좋아하는 이론: 작은 집합.2006년 4월 18일.
• 윌리엄 가스아치스파스 세트(Mahaney에 대한 트리뷰트).2007년 6월 29일.
• 복잡성 동물원: 스파스