13
$\begingroup$

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!

$\endgroup$
  • 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 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 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 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 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 at 13:21
-6
$\begingroup$

Answers:

(4) This construction actually exists before this post was made and was posted in several preprints (since December 25th, 2018): See here:

https://www.academia.edu/38094917/LOGSPACE_vs_P

https://zenodo.org/record/2549827

Abstract:

P versus NP is considered as one of the most important open problems in computer science. This consists in knowing the answer of the following question: Is P equal to NP? A precise statement of the P versus NP problem was introduced independently by Stephen Cook and Leonid Levin. Since that date, all efforts to find a proof for this problem have failed. Given a positive integer x and a collection S of positive integers, MAXIMUM is the problem of deciding whether x is the maximum of S where $S$ is represented by an array. We prove this problem is complete for P. Another major complexity classes are LOGSPACE and coNP. Whether LOGSPACE = P is a fundamental question that it is as important as it is unresolved. We show the problem MAXIMUM can be decided in logarithmic space. Consequently, we demonstrate the complexity class LOGSPACE is equal to P. We define a problem called CIRCUIT-MAXIMUM. CIRCUIT-MAXIMUM is nothing else but the instances of MAXIMUM represented by a positive integer x and a Boolean circuit C which represents the collection S. We show this version of MAXIMUM is in coNP-complete. In addition, CIRCUIT-MAXIMUM contains the instances of MAXIMUM that can be represented by an exponentially more succinct way. In this way, we show the succinct representation of a P-complete problem is indeed in coNP-complete. A succinct version of a problem that is complete for P (under restrictive-enough reducibilities) indeed can be shown not to lie in P, because it will be complete for EXP. Hence, it is possible this might be a good hint which could help us to prove the P versus NP problem.

$\endgroup$
  • $\begingroup$ I could be mistaken, but I think that w is not allowed to be part of the input for a projection. In other words, the algorithm $M$ cannot depend on $w$, but it can depend on the string length. This makes a projection more restrictive than a logspace reduction. $\endgroup$ – Michael Wehar Jan 13 at 8:16
  • $\begingroup$ I encourage you to take a look at the definition for a projection in: "On the (Non) NP-Hardness of Computing Circuit Complexity" $\endgroup$ – Michael Wehar Jan 13 at 8:17
  • $\begingroup$ I fixed the answer. $\endgroup$ – Frank Vega Jan 19 at 17:58

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.