6
$\begingroup$

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.

Improve this question
$\endgroup$
1
  • $\begingroup$ 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}$ $\endgroup$
    – user6973
    Jul 5, 2015 at 13:53

2 Answers 2

Reset to default
3
$\begingroup$

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

Improve this answer
$\endgroup$
0
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Technically true, but if I was the OP would restrict the problems to natural ones. $\endgroup$
    – Kaveh
    Jul 6, 2015 at 5:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.