Search

• < Previous
• 1
• Next >

Capturing Polynomial Time using Modular Decomposition

The question of whether there is a logic that captures polynomial time is one of the main open problems in descriptive complexity theory and database theory. In 2010 Grohe showed that fixed point logic with counting captures polynomial time on all classes of graphs with excluded minors. We now&nbsp;[&hellip;]