一項言語

計算複雑性理論では、単項言語またはタリー言語は、すべての文字列が 1 ^{k という}形式を持つ形式言語(文字列の集合)です。ここで、「1」は任意の固定記号です。たとえば、言語 {1, 111, 1111} は単項言語であり、言語 {1 ^k  |  kは素数} も同様です。このような言語の複雑性クラスは、 TALLYと呼ばれることもあります。

「単項」という名前は、単項言語が自然数の集合を単項記数法でエンコードしたものであるという事実に由来しています。任意の有限アルファベット上の文字列の宇宙は可算集合であるため、すべての言語は自然数の一意の集合 A にマッピングできます。したがって、すべての言語には単項バージョン{1 ^k  |  k in A} があります。逆に、すべての単項言語には、よりコンパクトなバイナリバージョン、つまり 1 ^{k が}言語に含まれる ような自然数kのバイナリエンコードのセットがあります。

複雑さは通常、入力文字列の長さで測定されるため、言語の単項バージョンは元の言語よりも「簡単」になることがあります。たとえば、言語が O(2 ⁿ ) 時間で認識できる場合、その単項バージョンは O( n ) 時間で認識できます。これは、 n が指数関数的に大きくなっているためです。より一般的には、言語が O(f( n )) 時間および O(g( n )) スペースで認識できる場合、その単項バージョンは O( n + f(log n )) 時間および O(g(log n )) スペースで認識できます (入力文字列を読み取るだけで O( n ) 時間が必要です)。ただし、言語のメンバーシップが決定不可能な場合は、その単項バージョンのメンバーシップも決定不可能です。

TALLYはP/polyに含まれています。これは、入力長のみに依存するアドバイス関数が与えられた場合に多項式時間で認識できる言語のクラスです。この場合、必要なアドバイス関数は非常に単純で、入力長kごとに 1 ビットを返し、 1 ^{k が}言語内に存在するかどうかを指定します。

単項言語は必然的にスパース言語です。これは、各nに対して長さnの値が最大で 1 つ、長さnの値が最大でn個含まれるためです。ただし、すべてのスパース言語が単項であるわけではありません。したがって、TALLY はSPARSEに含まれます。

NP困難な単項言語は存在しないと考えられている。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
• 複雑動物園：TALLY