scientific article; zbMATH DE number 1759437

MaRDI QIDQ4536386zbMATH OpenFDO

Authors Grégory Lafitte, Jacques Mazoyer

Publication date 4 November 2002

Mathematics Subject Classification ID

Consistency and independence results (03E35) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Descriptive complexity and finite models (68Q19)

Recommendations

• Infinite versions of some problems from finite complexity theory
• P ≠ NP ∩ co-NP for Infinite Time Turing Machines
• P NP for infinite time Turing machines
• The Complexity of Infinite Computations In Models of Set Theory
• On the computational complexity of infinite words.

Cited in

(2)

• Infinite versions of some problems from finite complexity theory
• For completeness, sublogarithmic space is no space.

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4536386)