<p>Not quite what you're looking for, but <a href="http://www.sciencedirect.com/science/article/pii/0890540189900084" rel="nofollow">the iterated mod problem is a P-complete number-theoretic decision problem</a>.</p>

CC BY-SA 3.0
2015-07-06T05:09:30.580Z
2015-07-06T05:09:30.580Z
William Hoza
<p>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}$.</p>

<p>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.</p>

CC BY-SA 3.0
2015-07-06T05:08:41.893Z
Technically true, but if I was the OP would restrict the problems to natural ones.
Kaveh
CC BY-SA 3.0
2015-07-06T04:52:07.903Z
2015-07-06T04:52:07.903Z
D.W.
<p>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)</p>

<p>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.</p>

<cc.complexity-theory><time-complexity><examples>
P-complete decision problems about integers
TigerSpots
# P-complete decision problems about integers

(Asked by: username_0 on 2015-07-05)

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.

**Tags:** cc.complexity-theory, time-complexity, examples

---

## 2 answers

### Answer by username_1 on 2015-07-06. Score: 3

Not quite what you're looking for, but [the iterated mod problem is a P-complete number-theoretic decision problem](http://www.sciencedirect.com/science/article/pii/0890540189900084).


---

### Answer by username_2 on 2015-07-06. Score: 0

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.

> **Comments:**
> **username_3**: Technically true, but if I was the OP would restrict the problems to natural ones.  

---

