Below is a sketch of what is known (or really, not known) about this question:
No “natural’’ example is known. Every P‐complete language one usually meets (CVP, alternating graph accessibility, circuit evaluation, Horn‐sat, linear‐inequalities feasibility, etc.) is in fact P‐hard under very weak reductions—projections or “first‐order‐definable” maps—and for all of those people have shown
Succinct-X is EXP-hard (indeed EXP-complete).
The Papadimitriou–Yannakakis “succinct graphs” paper you mention proves exactly:
If X is P‐hard under projections ⇒ Succinct-X is EXP-hard.
Thus one is driven to ask: what if X is P‐complete **only** under full logspace‐reductions and *not* under projections?
2. No separation of reduction‐types in P is known. Concretely, we do not know of any P‐complete X which fails to be P‐hard under projections. Equivalently:
“Does there exist a language X ∈ P such that
(a) X is P‐complete under log‐space reductions,
(b) X is *not* P‐hard under projections?
”
That’s open. If such an X existed then its succinct version would no longer be forcedEXP‐hard by the P‐hard‐under‐projections theorem, and *could* a priori lie in P.
3. Implications of finding such an X.
(a) You would have exhibited a clear separation between two notions of P‐completeness (log‐space vs. projection‐completeness).
(b) You would break the “succinct‐jump” theorem in a very concrete way: a P‐complete language whose succinct version does not climb to EXP.
(c) There is no known collapse of standard classes (no one is claiming P=EXP, or PH=EXP, etc.) merely from Succinct-X ∈ P; the barrier really is our inability to force any P‐complete problem off the projection‐complete list.
What about asking only for Succinct-X ∈ PH?
Again, everything known about the “succinct‐jump” is robust up to EXP, and there is no example today of a log‐space‐complete X whose succinct version even sits in PH. Weakening from “in P” to “in PH” does not make it any easier.
“Artificial” constructions under NP=L (or other collapses).
One can indeed cavalierly diagonalize or “bake in” an NPC oracle and then argue under NP=L that X ∈ L and hence X is P‐complete in a trivial way, yet Succinct-X collapses. But such languages are entirely non‐uniform, non‐natural, and in fact tell you nothing about the usual P vs. EXP barrier. They do not illuminate the real obstacle, which is our inability to separate log‐space vs. projection reducibilities within P.
In short:
• Answer to the main question: No such language is known, and it is widely regarded as open whether one can escape the EXP‐hardness of Succinct-X by giving up projections but retaining full log‐space completeness.
• Consequences if one were found:
You would exhibit a new phenomenon inside P (a P‐complete problem not projection‐hard), and show that the succinct‐representation trick does not universally boost P to EXP. Beyond that, there is no immediate collapse of mainstream classes.
• Still open if you only aim for Succinct-X ∈ PH.
• Artificial NP=L‐style pulls yield no insight into the genuine reduction‐theoretic barrier.
So, as of now, the succinct‐jump theorem stands unchallenged except by contrived, non‐natural examples, and finding a “real” P‐complete X with Succinct-X in P remains a clean open problem.
Was this answer helpful?
version: o4-mini-2025-04-16
Status: UQ Validated
Validated: 8 months ago
Status: Failed Human Verification
Verified: 7 months ago
Loading model reviews...
Loading reviews...