It is common to define $P$-completeness with respect to log-space many-one reductions.

I am looking for a complexity class $C \subseteq \mathsf{L}$ such that there are $\mathsf{P}$-complete problems w.r.t. many-one $C$-reductions.

What is the smallest known many-one reduction class $C$ such that HornSAT is complete for $\mathsf{P}$ under $C$-reductions?

The question was originally posted on CS with no answer.

  • $\begingroup$ Maybe you mean all non-trivial problems: the empty language and the language whose complement is empty cannot be complete. $\endgroup$ Commented Jul 29, 2015 at 13:58
  • $\begingroup$ @SashoNikolov Sure, I am not interested in trivial languages! $\endgroup$ Commented Jul 29, 2015 at 14:28
  • $\begingroup$ I don't understand the question. If C=P then all problems in P except the trivial ones are complete for P under C-reductions, and this is the case independent of what C is. $\endgroup$
    – Kaveh
    Commented Jul 29, 2015 at 15:30
  • $\begingroup$ @Kaveh What is the smallest such class $C$? For instance, is HornSAT complete for $P$ under $NC^1$ Reductions? $\endgroup$ Commented Jul 29, 2015 at 15:47
  • 1
    $\begingroup$ I share Kaveh’s confusion about the first paragraph. But concerning the blue question, a reasonable encoding of Horn-SAT is P-complete under DLOGTIME reductions. $\endgroup$ Commented Jul 29, 2015 at 17:09

1 Answer 1


It is easy to show that the Circuit Value Problem is complete for $\mathsf{P}$ under $\mathsf{AC^0}$ reductions (see András's comment below).

For an easier example consider $$A = \{\langle M,x,y\rangle \mid \text{$M$ accepts $x$ in $|y|$ steps} \}$$

If a class of reductions $C$ contains constant functions, pairing of strings, and functions where the size of their output can bound any polynomial; then $A$ is complete for $\mathsf{P}$ w.r.t. $C$.

  • 2
    $\begingroup$ For P-completeness of CVP under FO-reductions, see Exercise 3.28 in Immerman's Descriptive Complexity. $\endgroup$ Commented Jul 30, 2015 at 15:05

Your Answer

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

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