# P-complete decision problems about integers

Are there any known examples of P-complete decision problems which take as input a single integer? (non-unary, as unary feels like un-naturally forcing the issue)

It feels like there are many inherently sequential questions I could ask about an integer, but I don't know of any examples that have been shown to be P-complete.

• If there is a P-complete problem which takes "as input a single integer" in unary, then P is a $\hspace{.13 in}$ subset of the non-uniform version of the class with respect to which that problem is P-complete. $\;$ (So, for unary, there being such a problem would be at least somewhat surprising.) $\hspace{1.03 in}$ – user6973 Jul 5 '15 at 13:53

Not quite what you're looking for, but the iterated mod problem is a P-complete number-theoretic decision problem.

You can encode a pair (or triple, etc.) of integers as a single integer, using any number of standard techniques. In particular, there is an efficiently computable bijection $\varphi : \mathbb{N} \times \mathbb{N} \to \mathbb{N}$.

So, take any P-complete problem that take as input a constant number of integers, and you can convert it to a P-complete problem that takes as input a single integer.

• Technically true, but if I was the OP would restrict the problems to natural ones. – Kaveh Jul 6 '15 at 5:08