# Is there a P-complete language X such that succinct-X is in 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 $$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}$$?

(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!

• 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 Jan 10 at 12:00
• 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 Jan 10 at 17:11
• 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 supports Monica Jan 10 at 17:21
• 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 supports Monica Jan 11 at 8:02
• 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 supports Monica Jan 11 at 13:21