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.

$\endgroup$
  • $\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 '15 at 13:53
4
$\begingroup$

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

$\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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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