Quadratic sync problem

The quadratic sync problem is a problem designed by User:ais523 to be hard (possibly impossible) to solve efficiently, but easy to implement a brute-forcer for in even very simple programming languages. As such, it serves as a template for writing small programs in low-level languages whose halting behaviour is hard to predict.

Definition

A quadratic sync problem is a quintet of non-negative integers a, b, c, d, e.

A solution to a quadratic sync problem is a pair of non-negative integers x, y, such that ax²+bx+c=dy²+ey.

Difficulty

The wikipedia:Quadratic residuosity problem, which can be expressed as bx+c=y², is an example of a quadratic sync problem; specifically a quadratic sync problem with a=0, d=1, e=0. The quadratic residuosity problem has no known efficient solutions (i.e. the known solutions to it have a comparable time complexity to just brute-forcing possible values of x and y). That implies that the quadratic sync problem is unlikely to be efficiently solveable either.

Implementation

The sequence of possible values a×0²+b×0+c a×1²+b×1+c, a×2²+b×2+c, a×3²+b×3+c, etc. of the left hand side of a quadratic sync problem is just the cumulative sum of an arithmetic series (specifically, you start at c, then add b+1a, b+3a, b+5a, etc., i.e. the amount added is initially equal to a+b and increases by an additional 2a with each element). A similar principle applies to the right hand side. Thus, the problem collapses to the question of whether two sequences, each of which it's individually easy to generate, have any elements in common.

Because both sequences are strictly increasing sequences of integers, there are at least two simple (but inefficient) algorithms to brute-force solutions. One is to start with x=y=0 and repeatedly add 1 to x if the LHS is smaller, or y if the RHS is smaller, until the two sides are equal. The other is to try possible solutions one at a time from 0 upwards, constantly remembering how far it is to the next possible value of the LHS and of the RHS, and decreasing those values by 1 at each iteration (updating them whenever one side hits 0 but not the other); the advantage of this method is that x and y don't need to be directly stored anywhere (although if a and d are nonzero, they'll be stored indirectly, via the sizes of the gaps between possible LHS values and possible RHS values respectively). This makes the quadratic sync problem easy to implement in low-level and esoteric languages.

Computational class

The ability to encode the quadratic residuosity problem into the quadratic sync problem implies that the latter is at least as hard. Because it can potentially use unbounded values, it may well be harder; although ais523 would be mildly surprised if the problem turned out to be Turing-complete (more precisely, complete for recursively enumerable problems), there is no obvious reason why it can't be. It's therefore possible to view the problem as a language in its own right (that's either zero-dimensional or two-dimensional based on your point of view), rather than a problem to implement in other languages.

Viewed as a model of computation, the problem is a parameterized Diophantine equation in two unknowns with degree two. We can model it as P(a, b, c, d, e | x, y) = 0, with P being ax²+bx+c-dy²-ey = 0. Parameterized Diophantine equations model partial functions. While there exists a universal parameterized Diophantine equation with degree 10⁴⁴ and 10 unknowns, and a degree 4 equation with 58 unknowns, it is impossible to construct a universal quadratic Diophantine equation. This is because it is possible to determine if any quadratic Diophantine equation has solutions and what they are. This means that the quadratic Diophantine halting problem is solvable by an algorithm, therefore the quadratic sync problem is not Turing complete.

The exact computational power of this system is otherwise unknown.