Complexity of Linear Equations and Infinite Gadgets
Jan Grebík, Zoltán Vidnyánszky · 2025
Read Complexity of Linear Equations and Infinite Gadgets by Jan Grebík, Zoltán Vidnyánszky (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2501-06114.txt.
Description
Jan Grebík and Zoltán Vidnyánszky study how hard it is to tell if a family of linear equations can be solved. Their paper is from two thousand twenty-five. The equations are over a finite field, and the family is given in a Borel, or well-shaped, way. A past open question asked where the line falls between easy and hard cases of this kind.
They show the task is as hard as it can be in its class, in a strict sense from descriptive set theory. That result answers the open question. It also shows the split between easy and hard sits at a unlike place in the Borel world than in the classic constraint problem. The gap warns against porting that classic split over.
Catalog record
| CREATOR | Jan Grebík, Zoltán Vidnyánszky |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 32 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2501-06114