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!

  • 1
    $\begingroup$ 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. $\endgroup$ – Michaël Cadilhac Jan 10 '19 at 12:00
  • 1
    $\begingroup$ 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? $\endgroup$ – user3483902 Jan 10 '19 at 17:11
  • 2
    $\begingroup$ 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. $\endgroup$ – Emil Jeřábek Jan 10 '19 at 17:21
  • 1
    $\begingroup$ 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). $\endgroup$ – Emil Jeřábek Jan 11 '19 at 8:02
  • 1
    $\begingroup$ 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. $\endgroup$ – Emil Jeřábek Jan 11 '19 at 13:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.