<p>I came across a paper called "A Note on Succinct Representation of Graphs".  It seems that in the discussion section they claim that for any problem <span class="math-container">$X$</span> that is <span class="math-container">$\mathrm{P}$</span>-hard under projections, <span class="math-container">$\mbox{succinct-X}$</span> is <span class="math-container">$\mathrm{EXP}$</span>-hard.</p>

<p>This made me wonder if the theorem fails for more complicated kinds of reductions.  This led me to the following.</p>

<blockquote>
  <p><strong>My Question</strong></p>
  
  <p>Are there any problems <span class="math-container">$X$</span> such that <span class="math-container">$X$</span> is <span class="math-container">$\mathrm{P}$</span>-complete
  under logspace reductions and <span class="math-container">$\mbox{succinct-X}$</span> is in <span class="math-container">$\mathrm{P}$</span>?</p>
</blockquote>

<p><strong>Additional Questions:</strong></p>

<p>(1) If this is an open problem, then what are the implications if such an <span class="math-container">$X$</span> existed?</p>

<p>(2) If this is an open problem, is it still open is we weaken the requirement to <span class="math-container">$\mbox{succinct-X}$</span> in <span class="math-container">$PH$</span>?</p>

<p>(3) It seems that such an <span class="math-container">$X$</span> would also satisfy that <span class="math-container">$X$</span> is <span class="math-container">$\mathrm{P}$</span>-hard under logspace reductions, but not <span class="math-container">$\mathrm{P}$</span>-hard under projections.  Are such problems known to exist?</p>

<p>(4) I might be mistaken, but I think that I have a construction for such an <span class="math-container">$X$</span> assuming that <span class="math-container">$NP = L$</span>.  Would this be interesting?</p>

<p><strong>Note:</strong> I'm still learning about projections so please let me know if I made any mistakes.  Thank you!</p>

CC BY-SA 4.0
2019-01-10T12:00:58.210Z
My 2¢ here: Question 3 certainly looks like a prerequisite, so it may be worth asking separately.  If this doesn't get an answer, you may want to contact P-hardness specialists such as P. McKenzie.
Michaël Cadilhac
CC BY-SA 4.0
2019-01-10T17:11:18.787Z
what is a "projection" , does it pertain to reductions only - reductions with  logspace requirements have this property, or something that imposes succintness to the representation?
user3483902
CC BY-SA 4.0
2019-01-10T17:21:17.467Z
A simple padding argument shows that if $X$ is P-complete under dlogtime reductions, then succinct-$X$ is EXP-complete (in fact, still under dlogtime reductions). I thought at first this would generalize to less restrictive notions of reductions so that, e.g., P-completeness of $X$ under logspace reductions would imply  EXP-completess of succinct-$X$ under PSPACE reductions, but it does not seem to work that way; rather, it gives the EXP-completeness under polytime (or even more efficient) reductions of "PSPACE-succinct" $X$, if you get what I mean by that.
Emil Jeřábek
CC BY-SA 4.0
2019-01-10T20:21:27.477Z
@EmilJeřábek Thanks for the helpful comment!  So if I understand the first part correctly, the proof would go something like this? Given a language $X$ that is $P$-complete under dlogtime reductions and a language $L$ in $DTIME(2^n)$.  Consider padding $L$ to get a language $pad$-$L$.  Since $pad$-$L$ is in $P$, there is a dlogtime reduction $r$ from $pad$-$L$ to $X$.  We have that for every input string $x$, $x \in L$ iff $pad$-$x \in pad$-$L$ iff $\mbox{r(pad-x)} \in X$.
Michael Wehar
CC BY-SA 4.0
2019-01-10T20:21:31.143Z
@EmilJeřábek Now, although $x$ has length $n$ and $pad$-$x$ has length $2^n$, $pad$-$x$ can be encoded as a circuit of size $n$.  Further, because $r$ is in dlogtime, it can be represented by a circuit of size $n^2$ on inputs of size $2^n$.  And, it seems that we can somehow combine these two circuits to get a circuit $c$ of size roughly $n^3$ that encodes $\mbox{r(pad-x)}$ so that $x \in L$ iff $c \in \mbox{succinct-X}$.
Michael Wehar
CC BY-SA 4.0
2019-01-10T20:28:28.137Z
@EmilJeřábek In regards to the second part of your comment, did you mean the following?  If $X$ is $P$-complete under logspace reductions, it doesn't necessarily mean that $\mbox{succinct-X}$ is $EXP$-hard.  But, $\mbox{pspace-succinct-X}$ would be $EXP$-hard where $\mbox{pspace-succinct}$ is a more powerful notion of succinctness (that we haven't formally defined) that offers a higher compression ratio in some cases.
Michael Wehar
CC BY-SA 4.0
2019-01-10T20:46:33.170Z
@user3483902 Thank you very much for the good questions!  I'm still learning about projections so I think it's best if I refer you to a reference that includes a definition for time bounded projections: https://theoryofcomputing.org/articles/v013a004/
Michael Wehar
CC BY-SA 4.0
2019-01-10T20:48:16.593Z
@MichaëlCadilhac Thanks Michaël!  I appreciate the helpful suggestions.  :)
Michael Wehar
CC BY-SA 4.0
2019-01-11T08:02:57.373Z
Yes, that's it. (Note that logtime Turing machines are defined so that they receive input by means of a query tape that requests individual bits instead of the usual input tape, hence they readily take input represented by a circuit.) For pspace-succinct-$X$, one can take a variant of succinct-$X$ where the input is not represented by an ordinary Boolean circuit, but by a quantified Boolean formula (or circuit).
Emil Jeřábek
CC BY-SA 4.0
2019-01-11T09:13:44.150Z
@EmilJeřábek Thank you for the clarification!  I really appreciate it.
Michael Wehar
CC BY-SA 4.0
2019-01-11T13:21:46.190Z
Seeing that projections are a restricted class of polylogtime reductions, let me add that what I wrote above about logtime reductions also applies to polylogtime reductions.
Emil Jeřábek
CC BY-SA 4.0
2019-01-11T19:34:46.973Z
@EmilJeřábek Yes, I noticed this too.  :)
Michael Wehar
CC BY-SA 4.0
2019-05-28T05:25:07.933Z
Werent p-projections used in Valiants' original completeness and algebra paper?
user3483902
<cc.complexity-theory><complexity-classes><reductions><succinct>
Is there a P-complete language X such that succinct-X is in P?
Michael Wehar
# Is there a P-complete language X such that succinct-X is in P?

(Asked by: username_0 on 2019-01-10)

I came across a paper called "A Note on Succinct Representation of Graphs". It seems that in the discussion section they claim that for any problem $X$ that is $\mathrm{P}$-hard under projections, $\mbox{succinct-X}$ is $\mathrm{EXP}$-hard.

This made me wonder if the theorem fails for more complicated kinds of reductions. This led me to the following.

> **My Question**
>
> Are there any problems $X$ such that $X$ is $\mathrm{P}$-complete
> under logspace reductions and $\mbox{succinct-X}$ is in $\mathrm{P}$?

**Additional Questions:**

(1) If this is an open problem, then what are the implications if such an $X$ existed?

(2) If this is an open problem, is it still open is we weaken the requirement to $\mbox{succinct-X}$ in $PH$?

(3) It seems that such an $X$ would also satisfy that $X$ is $\mathrm{P}$-hard under logspace reductions, but not $\mathrm{P}$-hard under projections. Are such problems known to exist?

(4) I might be mistaken, but I think that I have a construction for such an $X$ assuming that $NP = L$. Would this be interesting?

**Note:** I'm still learning about projections so please let me know if I made any mistakes. Thank you!

**Tags:** cc.complexity-theory, complexity-classes, reductions, succinct
> **Comments:**
> **username_1**: My 2¢ here: Question 3 certainly looks like a prerequisite, so it may be worth asking separately.  If this doesn't get an answer, you may want to contact P-hardness specialists such as P. McKenzie.  
> **username_2**: what is a "projection" , does it pertain to reductions only - reductions with  logspace requirements have this property, or something that imposes succintness to the representation?  
> **username_3**: A simple padding argument shows that if $X$ is P-complete under dlogtime reductions, then succinct-$X$ is EXP-complete (in fact, still under dlogtime reductions). I thought at first this would generalize to less restrictive notions of reductions so that, e.g., P-completeness of $X$ under logspace reductions would imply  EXP-completess of succinct-$X$ under PSPACE reductions, but it does not seem to work that way; rather, it gives the EXP-completeness under polytime (or even more efficient) reductions of "PSPACE-succinct" $X$, if you get what I mean by that.  
> **username_0**: @EmilJeřábek Thanks for the helpful comment!  So if I understand the first part correctly, the proof would go something like this? Given a language $X$ that is $P$-complete under dlogtime reductions and a language $L$ in $DTIME(2^n)$.  Consider padding $L$ to get a language $pad$-$L$.  Since $pad$-$L$ is in $P$, there is a dlogtime reduction $r$ from $pad$-$L$ to $X$.  We have that for every input string $x$, $x \in L$ iff $pad$-$x \in pad$-$L$ iff $\mbox{r(pad-x)} \in X$.  
> **username_0**: @EmilJeřábek Now, although $x$ has length $n$ and $pad$-$x$ has length $2^n$, $pad$-$x$ can be encoded as a circuit of size $n$.  Further, because $r$ is in dlogtime, it can be represented by a circuit of size $n^2$ on inputs of size $2^n$.  And, it seems that we can somehow combine these two circuits to get a circuit $c$ of size roughly $n^3$ that encodes $\mbox{r(pad-x)}$ so that $x \in L$ iff $c \in \mbox{succinct-X}$.  
> **username_0**: @EmilJeřábek In regards to the second part of your comment, did you mean the following?  If $X$ is $P$-complete under logspace reductions, it doesn't necessarily mean that $\mbox{succinct-X}$ is $EXP$-hard.  But, $\mbox{pspace-succinct-X}$ would be $EXP$-hard where $\mbox{pspace-succinct}$ is a more powerful notion of succinctness (that we haven't formally defined) that offers a higher compression ratio in some cases.  
> **username_0**: @user3483902 Thank you very much for the good questions!  I'm still learning about projections so I think it's best if I refer you to a reference that includes a definition for time bounded projections: https://theoryofcomputing.org/articles/v013a004/  
> **username_0**: @MichaëlCadilhac Thanks Michaël!  I appreciate the helpful suggestions.  :)  
> **username_3**: Yes, that's it. (Note that logtime Turing machines are defined so that they receive input by means of a query tape that requests individual bits instead of the usual input tape, hence they readily take input represented by a circuit.) For pspace-succinct-$X$, one can take a variant of succinct-$X$ where the input is not represented by an ordinary Boolean circuit, but by a quantified Boolean formula (or circuit).  
> **username_0**: @EmilJeřábek Thank you for the clarification!  I really appreciate it.  
> **username_3**: Seeing that projections are a restricted class of polylogtime reductions, let me add that what I wrote above about logtime reductions also applies to polylogtime reductions.  
> **username_0**: @EmilJeřábek Yes, I noticed this too.  :)  
> **username_2**: Werent p-projections used in Valiants' original completeness and algebra paper?  

---

## 0 answers

