The NIP characterization of tractable model-checking on hereditary classes
Let be a hereditary class of relational structures. Here, model-checking on is tractable if there is an algorithm that, on input a structure and an -sentence , decides whether in time for some computable function . The class is NIP if its theory does not have the independence property. NIP characterization of tractability. The model-checking problem on is fixed-parameter tractable if, and only if, is NIP. All known hereditary classes of graphs and relational structures with tractable model-checking are NIP, and the conjecture proposes that NIP is also necessary for tractability in every hereditary class.
References
- Samuel Braunfeld, Anuj Dawar, Ioannis Eleftheriadis and Aris Papadopoulos, “Monadic NIP in monotone classes of relational structures”, arXiv:2302.05695 (2023).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
No solutions have been posted yet.