| 翻訳と辞書 |
FO (complexity)
In descriptive complexity, a branch of computational complexity, ''FO'' is a complexity class of structures which can be recognized by formulas of first-order logic, and also equals the complexity class AC0. Descriptive complexity uses the formalism of logic, but does not use several key notions associated with logic such as proof theory or axiomatization.
Restricting predicates to be from a set ''X'' yields a smaller class ''FO()''. For instance, ''FO()'' is the set of star-free languages. The two different definitions of ''FO()'', in terms of logic and in terms of regular expressions, suggests that this class may be mathematically interesting beyond its role in computational complexity, and that methods from both logic and regular expressions may be useful in its study.
Similarly, extensions of FO formed by the addition of operators give rise to other well-known complexity classes. This allows the complexity of some problems to be established without reference to algorithms.
== Definition and examples ==
抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』
■ウィキペディアで「FO (complexity)」の詳細全文を読む
スポンサード リンク
| 翻訳と辞書 : 翻訳のためのインターネットリソース |
Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.
|
|