단어

계산 복잡성 이론에서 단일 언어 또는 집계 언어는 모든 문자열이 1 형식을^k 갖는 공식 언어(현악 집합)이며 여기서 "1"은 어떤 고정 기호도 될 수 있다.예를 들어 {1, 111, 1111} 언어는 단항이며 {1k는^k prime} 언어와 같다.그러한 모든 언어의 복잡성 클래스를 TALIGE라고 부르기도 한다.

"유나리"라는 명칭은 단나리어가 단나리 수 체계에서 자연수 집합의 인코딩이라는 사실에서 유래되었다.어떤 유한한 알파벳에 걸친 문자열의 우주가 계수 가능한 집합이기 때문에, 모든 언어는 고유 집합인 자연수 A에 매핑될 수 있다. 따라서, 모든 언어에는 단일 버전 {1k^k in A}이 있다.반대로, 모든 단항 언어는 1이^k 언어에 있는 자연 숫자 k의 이진 암호들의 집합인 보다 컴팩트한 이진 버전을 가지고 있다.

일반적으로 입력 문자열의 길이에 따라 복잡성을 측정하기 때문에 언어의 단항 버전은 원래 언어보다 "쉬울" 수 있다.예를 들어, 어떤 언어를 O(2ⁿ) 시간에 인식할 수 있다면, 그 단항 버전은 O(n) 시간에 인식될 수 있는데, 왜냐하면 n은 기하급수적으로 커졌기 때문이다.보다 일반적으로 언어를 O(f(n)시간과 O(g)공간에서 인식할 수 있는 경우, 언어의 단일 버전은 O(n + f(log n)시간과 O(g(log n)공간(우리는 입력 문자열을 읽는 것만으로 O(n)시간이 필요하다)시간에서 인식될 수 있다.그러나, 언어의 멤버십이 불독이라면, 그것의 단일 버전의 멤버십도 불독이다.

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

TALIGE는 입력 길이에만 의존하는 조언 함수가 주어진 다항 시간 내에 인식할 수 있는 언어의 종류인 P/poly에 포함되어 있다.이 경우 필요한 조언 함수는 매우 간단하다. 이 함수는 1이^k 언어인지 여부를 지정하는 각 입력 길이 k에 대해 단일 비트를 반환한다.

단항 언어는 각 n에 대해 최대 하나의 길이 n 값과 최대 길이 n 값을 포함하지만, 모든 희박한 언어가 단항인 것은 아니기 때문에 반드시 희소 언어인 것이다. 따라서 TALU는 스파스에 포함되어 있다.

NP-hard 단항 언어가 없다고 믿는데, NP-완전한 단항 언어가 존재한다면 P = NP이다.^[1]

이 결과는 희박한 언어로 확장될 수 있다.^[2]

L이 단항어라면 L*(L의 클레인 스타)는 정규어다.^[3]

집계 클래스

복잡도 등급 P는₁ 다항 시간 튜링 기계(단항 시간 튜링 기계로 입력된 경우)로 인식할 수 있는 단항 언어의 등급이며, 클래스 P의 아날로그다.단항 설정에서 NP의 아날로그는 NP이다₁.#P의 아날로그인 셈 클래스 #P도₁ 알려져 있다.^[4]

참조

메모들

일반참조

• 랜스 포트나우가장 좋아하는 이론: 작은 집합.2006년 4월 18일.http://weblog.fortnow.com/2006/04/favorite-theorems-small-sets.html
• 복잡성 동물원: TALIGE