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$ Jul 29 '15 at 13:58
  • $\begingroup$ @SashoNikolov Sure, I am not interested in trivial languages! $\endgroup$ Jul 29 '15 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
    Jul 29 '15 at 15:30
  • $\begingroup$ @Kaveh What is the smallest such class $C$? For instance, is HornSAT complete for $P$ under $NC^1$ Reductions? $\endgroup$ Jul 29 '15 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$ Jul 29 '15 at 17:09

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$ Jul 30 '15 at 15:05

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.