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

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

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

CC BY-SA 3.0
2015-07-30T15:05:50.433Z
For P-completeness of CVP under FO-reductions, see Exercise 3.28 in Immerman's _Descriptive Complexity_.
András Salamon
CC BY-SA 3.0
2015-07-29T20:35:11.113Z
2015-07-30T17:19:22.613Z
2015-07-30T17:19:22.613Z
Kaveh
<p>It is common to define $P$-completeness with respect to log-space many-one reductions.</p>

<p>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. </p>

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

<p>The question was originally posted on <a href="https://cs.stackexchange.com/questions/37562/weakest-reduction-for-p-completeness">CS</a> with no answer.</p>

CC BY-SA 3.0
2015-07-29T13:58:01.453Z
Maybe you mean all non-trivial problems: the empty language and the language whose complement is empty cannot be complete.
Sasho Nikolov
CC BY-SA 3.0
2015-07-29T14:28:02.177Z
@SashoNikolov  Sure, I am not interested in trivial languages!
Mohammad Al-Turkistany
CC BY-SA 3.0
2015-07-29T15:30:32.597Z
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.
Kaveh
CC BY-SA 3.0
2015-07-29T15:47:46.137Z
@Kaveh What is the smallest such class $C$? For instance, is HornSAT complete for $P$ under $NC^1$ Reductions?
Mohammad Al-Turkistany
CC BY-SA 3.0
2015-07-29T16:13:52.673Z
Edited post to remove confusion.
Mohammad Al-Turkistany
CC BY-SA 3.0
2015-07-29T17:09:15.693Z
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.
Emil Jeřábek
CC BY-SA 3.0
2015-07-29T18:29:52.950Z
@EmilJeřábek I edited the paragraph to address your and others comments. I am looking for reductions weaker than $L$ such as $NC^1$.
Mohammad Al-Turkistany
CC BY-SA 3.0
2015-07-29T18:54:30.437Z
As Email wrote. I don't know any natural P-complete problem which is not complete under AC0 reductions and one can go to even weaker reductions I think. Since reductions between complete problems can typically be computed in AC0, as soon as we have a complete problem under AC0 (e.g. CircuitValue) all of them become complete under AC0 reductions.
Kaveh
CC BY-SA 3.0
2015-07-29T19:15:43.990Z
@Kaveh Do you have a reference for AC0 reductions? Please convert your comment into an answer.
Mohammad Al-Turkistany
CC BY-SA 3.0
2015-07-29T19:35:47.520Z
I don't have a reference off my head.
Kaveh
<cc.complexity-theory><complexity-classes>
What is the smallest class of reductions under which there is a $\mathsf{P}$-complete problem?
Mohammad Al-Turkistany
# What is the smallest class of reductions under which there is a $\mathsf{P}$-complete problem?

(Asked by: username_0 on 2015-07-29)

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](https://cs.stackexchange.com/questions/37562/weakest-reduction-for-p-completeness) with no answer.

**Tags:** cc.complexity-theory, complexity-classes

> **Comments:**
> **username_1**: Maybe you mean all non-trivial problems: the empty language and the language whose complement is empty cannot be complete.  
> **username_0**: @SashoNikolov  Sure, I am not interested in trivial languages!  
> **username_2**: 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.  
> **username_0**: @username_2 What is the smallest such class $C$? For instance, is HornSAT complete for $P$ under $NC^1$ Reductions?  
> **username_0**: Edited post to remove confusion.  
> **username_3**: I share username_2’s confusion about the first paragraph. But concerning the blue question, a reasonable encoding of Horn-SAT is P-complete under DLOGTIME reductions.  
> **username_0**: @EmilJeřábek I edited the paragraph to address your and others comments. I am looking for reductions weaker than $L$ such as $NC^1$.  
> **username_2**: As Email wrote. I don't know any natural P-complete problem which is not complete under AC0 reductions and one can go to even weaker reductions I think. Since reductions between complete problems can typically be computed in AC0, as soon as we have a complete problem under AC0 (e.g. CircuitValue) all of them become complete under AC0 reductions.  
> **username_0**: @username_2 Do you have a reference for AC0 reductions? Please convert your comment into an answer.  
> **username_2**: I don't have a reference off my head.  

---

## 1 answers

### Answer by username_2 on 2015-07-29. Score: 7 | Accepted answer

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

> **Comments:**
> **username_4**: For P-completeness of CVP under FO-reductions, see Exercise 3.28 in Immerman's _Descriptive Complexity_.  

---

