語言複雜性類

語言複雜性類(complexity class of languages一種複雜性類.指具有特定複雜性的語言組成之集合.設藝為有窮字母表，所謂藝上的語言，是指由藝上的字(即有窮字母串)組成之集合.設M為一個算法，}M為其複雜性測度，L為M所接受的語言.若存在函式t，使對任何。EL，都有}M(Q><t( }川)，則稱L為M關於}M以t為界函式而接受的語言.並稱L是具有複雜性t的語言.所有具有複雜性t的語言組成之類}(t)稱為t的語言複雜性類.此時，t稱為}(t)之名或界函式.若F為函式集合，此(F>= U }}(t> I t E F}稱為F的(語言)複雜性類.