#complexity
5 resultsA Universality Theorem for Nested Polytopes
Michael G. Dobbins, Andreas Holmsen, Tillmann Miltzow
The paper proves a universality theorem showing that solving nested polytope instances is equivalent to solving arbitrary systems of polynomial equations, and consequently establis…
Geometry and Generation of a New Graph Planarity Game
Rutger Kraaijer, Marc van Kreveld, Wouter Meulemans +1
The paper introduces Swap Planarity, a puzzle where vertices connected by an edge are swapped to eliminate edge crossings, and studies its properties, generation of high-quality in…
Toward Understanding Catastrophic Forgetting in Continual Learning
Cuong V. Nguyen, Alessandro Achille, Michael Lam +3
The paper investigates how properties of task sequences, such as total complexity and sequential heterogeneity, influence catastrophic forgetting in continual learning algorithms u…
On Cycle Transversals and Their Connected Variants in the Absence of a Small Linear Forest
Konrad K. Dabrowski, Carl Feghali, Matthew Johnson +3
The paper establishes polynomial‑time algorithms for Feedback Vertex Set, Odd Cycle Transversal and their connected variants on (sP1+P3)-free graphs and cographs, and shows NP‑comp…
Generating theorem proving procedures from axioms of Truncated Predicate Calculus
Grzegorz Wiaderek, Iwona Skalna
The paper introduces a method for automatically generating polynomial‑time decision procedures from axioms of a restricted fragment called Truncated Predicate Calculus, and demonst…