Your browser does not fully support modern features. Please upgrade for a smoother experience.
Submitted Successfully!
+1 credit
Thank you for your contribution! You can also upload a video entry or images related to this topic.
For video creation, please contact our Academic Video Service.
| Version | Summary | Created by | Modification | Content Size | Created at | Operation |
|---|---|---|---|---|---|---|
| 1 | Rita Xu | -- | 2237 | 2022-11-02 01:30:47 |
Video Upload Options
We provide professional Academic Video Service to translate complex research into visually appealing presentations. Would you like to try it?
Cite
If you have any further questions, please contact Encyclopedia Editorial Office.
HandWiki. FO (Complexity). Encyclopedia. Available online: https://encyclopedia.pub/entry/32619 (accessed on 14 October 2026).
HandWiki. FO (Complexity). Encyclopedia. Available at: https://encyclopedia.pub/entry/32619. Accessed October 14, 2026.
HandWiki. "FO (Complexity)" Encyclopedia, https://encyclopedia.pub/entry/32619 (accessed October 14, 2026).
HandWiki. (2022, November 03). FO (Complexity). In Encyclopedia. https://encyclopedia.pub/entry/32619
HandWiki. "FO (Complexity)." Encyclopedia. Web. 03 November, 2022.
Copy Citation
In descriptive complexity, a branch of computational complexity, FO is a complexity class of structures that 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[X]. For instance, FO[Similarly, extensions of first-order logic 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.
fosimilarly
first-order logic
axiomatization
References
- Immerman, Neil (1986). "Relational queries computable in polynomial time" (in en). Information and Control 68 (1–3): 86–104. doi:10.1016/s0019-9958(86)80029-8. https://dx.doi.org/10.1016%2Fs0019-9958%2886%2980029-8
- Vardi, Moshe Y. (1982). The Complexity of Relational Query Languages (Extended Abstract). STOC '82. New York, NY, USA: ACM. 137–146. doi:10.1145/800070.802186. ISBN 978-0897910705. https://dx.doi.org/10.1145%2F800070.802186
- Serge Abiteboul, Moshe Y. Vardi, Victor Vianu: Fixpoint logics, relational machines, and computational complexity Journal of the ACM archive, Volume 44 , Issue 1 (January 1997), Pages: 30-56, ISSN 0004-5411 http://portal.acm.org/citation.cfm?id=256295
More
Information
Subjects:
Others
Contributor
MDPI registered users' name will be linked to their SciProfiles pages. To register with us, please refer to https://encyclopedia.pub/register
:
View Times:
942
Entry Collection:
HandWiki
Revision:
1 time
(View History)
Update Date:
03 Nov 2022
Table of Contents
Notice
You are not a member of the advisory board for this topic. If you want to update advisory board member profile, please contact office@encyclopedia.pub.
OK
Confirm
Only members of the Encyclopedia advisory board for this topic are allowed to note entries. Would you like to become an advisory board member of the Encyclopedia?
Yes
No
${ textCharacter }/${ maxCharacter }
Submit
Cancel
Back
Comments
${ item }
|
${ item.createdUser.fullName }
${ item.createdAt }
${ item.vote }
${ item.reply }
Delete
${ reply.createdUser.fullName }
${ reply.createdAt }
${ reply.vote }
Delete
There is no reply to this comment~
${ item.replyTextCharacter }/${ item.replyMaxCharacter }
Submit
Cancel
More
No more~
There is no comment~
${ textCharacter }/${ maxCharacter }
Submit
Cancel
${ selectedItem.replyTextCharacter }/${ selectedItem.replyMaxCharacter }
Submit
Cancel
Confirm
Are you sure to Delete?
Yes
No