8
$\begingroup$

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.

Improve this question
$\endgroup$
10
  • $\begingroup$ Maybe you mean all non-trivial problems: the empty language and the language whose complement is empty cannot be complete. $\endgroup$
    – Sasho Nikolov
    Jul 29, 2015 at 13:58
  • $\begingroup$ @SashoNikolov Sure, I am not interested in trivial languages! $\endgroup$
    – Mohammad Al-Turkistany
    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
    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$
    – Mohammad Al-Turkistany
    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$
    – Emil Jeřábek
    Jul 29, 2015 at 17:09

1 Answer 1

Reset to default
7
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • 2
    $\begingroup$ For P-completeness of CVP under FO-reductions, see Exercise 3.28 in Immerman's Descriptive Complexity. $\endgroup$
    – András Salamon
    Jul 30, 2015 at 15:05

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.