The Descriptive Complexity of Relation Modification Problems

Florian Chudigiewitsch, Marlene Gr\"undel, Christian Komusiewicz, Nils Morawietz, Till Tantau
https://arxiv.org/abs/2603.22043 https://arxiv.org/pdf/2603.22043 https://arxiv.org/html/2603.22043

arXiv:2603.22043v1 Announce Type: new
Abstract: A relation modification problem gets a logical structure and a natural number k as input and asks whether k modifications of the structure suffice to make it satisfy a predefined property. We provide a complete classification of the classical and parameterized complexity of relation modification problems - the latter w. r. t. the modification budget k - based on the descriptive complexity of the respective target property. We consider different types of logical structures on which modifications are performed: Whereas monadic structures and undirected graphs without self-loops each yield their own complexity landscapes, we find that modifying undirected graphs with self-loops, directed graphs, or arbitrary logical structures is equally hard w. r. t. quantifier patterns.
Moreover, we observe that all classes of problems considered in this paper are subject to a strong dichotomy in the sense that they are either very easy to solve (that is, they lie in paraAC^{0\uparrow} or TC^0) or intractable (that is, they contain W[2]-hard or NP-hard problems).

toXiv_bot_toot

Autoritäre Systeme beginnen selten mit Gewalt. Sie beginnen mit Ritualen, Fahnenappellen, Liedern und Lehrplänen. Mit Sätzen, die in Klassenzimmern gesprochen werden, bis sie wie Wahrheit klingen. Der Film von David Borenstein und Pawel Talankin versteht die banale Mechanik der Macht erstaunlich gut. Nicht als spektakuläre Enthüllung, sondern als langsame Verschiebung der Wirklichkeit. Es kommt nicht oft vor, dass Sie einen Oscar prämierten Dokumentarfilm bereits vor der Preisverleihung schon in der Mediathek sehen können. Noch dazu einen, der vom @ZDF und ARTE koproduziert wurde. (ARTE, Neu!)

Modal Fragments

Nick Bezhanishvili, Balder ten Cate, Arunavo Ganguly, Arne Meier
https://arxiv.org/abs/2603.05055 https://arxiv.org/pdf/2603.05055 https://arxiv.org/html/2603.05055

arXiv:2603.05055v1 Announce Type: new
Abstract: We survey systematic approaches to basis-restricted fragments of propositional logic and modal logics, with an emphasis on how expressive power and computational complexity depend on the allowed operators. The propositional case is well-established and serves as a conceptual template: Post's lattice organizes fragments via Boolean clones and supports complexity classifications for standard reasoning tasks. For modal fragments, we then bring together two historically independent lines of investigation: a general framework where modal fragments are parameterized by a basis of "connectives" defined by arbitrary modal formulas (initially proposed and studied by logicians such as Kuznetsov and Ratsa in the 1970s), and the more tractable class of what we call simple modal fragments parameterized by Boolean functions plus selected modal operators, where Post-lattice methods enable systematic decidability and dichotomy results. Along the way, we collect and extend results on teachability and exact learnability from examples for both propositional fragments and simple modal fragments, and we conclude by identifying several open problems.

toXiv_bot_toot

Klicks wie Nikotin: Social-Media-Konzerne stehen erstmals vor Gericht, weil sie Jugendliche süchtig machen
https://www.nzz.ch/technologie/der-tabak-moment-von-social-media-junge-erwachsene-beschuldigen-instagram-tiktok-und-co-sie-suechtig-gemacht-zu-haben-ld.1923401?utm_source=flipboard&utm_medium=activitypub

Gepostet in Technologie @technologie-NZZ_Ch

In recent weeks there have been a number of examples of Erdos problems that were solved more or less autonomously by an AI tool, only to find out that the problem had already been solved years ago in the literature: https://www.erdosproblems.com/897 https://www.erdosproblems.com/333 https://www.erdosproblems.com/481 .

One possible explanation for this is contamination: that the solutions to each of these problems were somehow picked up by the training data for the AI tools and encoded within its weights. However, other AI deep research tools failed to pick up these connections, so I am skeptical that this is the full explanation for the above events.

My theory is that the AI tools are now becoming capable enough to pick off the lowest hanging fruit amongst the problems listed as open in the Erdos problem database, where by "lowest hanging" I mean "amenable to simple proofs using fairly standard techniques". However, that category is also precisely the category of nominally open problems that are most likely to have been solved in the literature, perhaps without much fanfare due to the simple nature of the arguments. This may already explain much of the strong correlation above between AI-solvability and being already proven in some obscure portion of the literature.

This correlation is likely to continue in the near term, particularly for problems attacked purely by AI tools without significant expert supervision. Nevertheless, the amount of progress in capability of these tools is non-trivial, and bodes well for the ability of such tools to automatically scan through the "long tail" of underexamined problems in the mathematical literature.

When Symmetry Yields NP-Hardness: Affine ML-SAT on S5 Frames

Andreas Krebs, Arne Meier
https://arxiv.org/abs/2512.17378 https://arxiv.org/pdf/2512.17378 https://arxiv.org/html/2512.17378

arXiv:2512.17378v1 Announce Type: new
Abstract: Hemaspaandra~et~al.~[JCSS 2010] conjectured that satisfiability for multi-modal logic restricted to the connectives XOR and 1, over frame classes T, S4, and S5, is solvable in polynomial time. We refute this for S5 frames, by proving NP-hardness.

toXiv_bot_toot