The study of Succinct representation of graphs was initiated by Galperin and Wigderson in a paper from 1983, where they prove that for many simple problems like finding a triangle in a graph, the corresponding succinct version in $\mathsf{NP}$-complete. Papadimitriou and Yanakkakis further this line of research, and prove that for a problem $\Pi$ which is $\mathsf{NP}$-complete/$\mathsf{P}$-complete, the corresponding Succinct version, namely Succinct $\Pi$ is respectively, $\mathsf{NEXP}$-complete and $\mathsf{EXP}$-complete. (They also show that if $\Pi$ is $\mathsf{NL}$-complete, then Succinct $\Pi$ is $\mathsf{PSPACE}$-complete.

Now my question is, are there any problems $\Pi$ known for which, the corresponding Succinct version is in $\mathsf{P}$? I'd be interested in knowing about any other related results(both positive and impossibility results, if any) which I might have missed above. (I couldn't locate anything of interest by a google search, since search words like succinct, representation, problems, graphs lead to just almost any complexity result! :))

  • $\begingroup$ what kind of problem are you looking for? surely, some trivial graph properties remain trivial in the succinct version as well, e.g. the property satisfied by every graph as well as the property satisfied by no graph. maybe you are looking for any property except these two? $\endgroup$ – Sasho Nikolov Feb 21 '12 at 18:53
  • 2
    $\begingroup$ First I wanted to mention that the results of Papadimitriou and Yannakakis require completeness for a special kind of reduction. (Yet their result can be applied to a huge number of problems.) $\endgroup$ – Bruno Feb 21 '12 at 19:51
  • 2
    $\begingroup$ Now about your question: Since you have an exponential blow-up in the complexity of the succinct version of a problem (in general), it would probably imply that your original problem in solvable in logarithmic time? But then a problem solvable in logarithmic time can actually be solved in constant time. Therefore, the succinct version can also be solved in constant time. I am quite convinced that my above "argument" has too many gaps to be entirely correct, but at least it means that your problems need to be very special at the beginning. $\endgroup$ – Bruno Feb 21 '12 at 19:56
  • $\begingroup$ @SashoNikolov Naturally, I am looking for non-trivial graph properties. I found it quite surprising initially that checking if a graph has a triangle would be $\mathsf{NP}$-complete! In fact, if you consider the problem of detecting if an input string has a $1$ is exactly the Circuit Satisfiability problem in the Succint world(Check Ryan's casual tour survey of his lower bound for an interesting discussion). This particular example was what prompted me to think if there can be any problem whose succint version is in P. $\endgroup$ – Nikhil Feb 21 '12 at 20:14
  • $\begingroup$ @Bruno I was thinking on the same lines, but I couldn't immediately come up with a concrete example yet! $\endgroup$ – Nikhil Feb 21 '12 at 20:18

Here is an interesting problem whose succinct version has interesting properties. Define Circuit-Size-$2^{n/2}$ to be the problem: given a Boolean function as a $2^n$-bit string, does this function have a circuit of size at most $2^{n/2}$? Note this problem is in $NP$.

One way to define Succinct-Circuit-Size-$2^{n/2}$ would be: for a constant $k$, given an $n$-input, $n^k$-size circuit $C$, we want to know if its truth table is an instance of Circuit-Size-$2^{n/2}$. But this is a trivial problem: all inputs which are actual circuits are yes-instances. So this problem is in $P$.

A more general way to define Succinct-Circuit-Size-$2^{n/2}$ would be: we are given an arbitrary circuit $C$ and want to know if its truth table encodes an instance of Circuit-Size-$2^{n/2}$. But if $n$ is the number of inputs to $C$, $m$ is the size of $C$, and $m \leq 2^{n/2}$, we can automatically accept: the input itself is a witness for the language. Otherwise, we have $m \geq 2^{n/2}$. In that case, the input length $m$ is already huge, so we can try all possible $2^n$ assignments in $m^{O(1)}$ time, obtain the truth table of the function, and now we are back to the original $NP$ problem again. So this is a problem in $NP$ whose succinct version is also in $NP$.

This problem is believed to be not $NP$-hard; see the paper by Kabanets and Cai (http://www.cs.sfu.ca/~kabanets/Research/circuit.html)

  • 2
    $\begingroup$ this is very nice, and tears apart any intuition i thought i had.. $\endgroup$ – Sasho Nikolov Mar 7 '12 at 4:11

Given that even deciding whether the graph represented by a given succinct representation contains at least one edge or not is equivalent to Circuit SAT and therefore NP-complete, it is tempting to claim that any interesting property of a succinct representation should be NP-hard under a suitable definition of “interesting.” This claim would be a complexity-theoretic analog for Rice’s theorem. Alas, finding the most general complexity-theoretic analog of Rice’s theorem is an open problem, although there are results which give some forms of such complexity-theoretic analogs.

  • $\begingroup$ Thanks for the pointer! That was a great answer by Russell on the question you linked! $\endgroup$ – Nikhil Feb 22 '12 at 9:36

I didn't mean this to be an answer but it would require too many comments. Hope it's useful.

As Tsuyoshi points out, it's tempting to conjecture that all "non-trivial" properties are hard (NP-hard for example). However, to show this, you need to define non-trivial. In Rice's theorem, the nontrivial properties are all properties except the property which includes all computably enumerable languages and the property which includes no computably enumerable language. It's less clear what the right definition of non-trivial is for succinct problems. Definitely the properties which contain all strings or no strings are in P. But there are others in P as well. For example, the property $\Pi$ that matches strings whose middle bit is 0. Or $\Pi$ contains all strings of $2^n$ bits such that every $2^n/x$-th bit is 1, where $x = n^{O(1)}$. So how do we define "trivial" to encompass this type of properties?

One idea is to look at those $\Pi$ which are "symmetric": if a string $s$ is in $\Pi$, then any permutation of the bits of $s$ is also in $\Pi$. Such properties depend only on the number of 1 bits in a string. In an answer to the question Tsuyoshi linked, Ryan Williams gives a link to this paper which shows that all such problems are UP-hard.

Other ideas how to define "non-trivial property"? We can look at $\Pi$ as a family of boolean functions (the indicator functions of the property for each string length). It seems to me that the non-trivial properties are those for which the corresponding family of boolean functions has non-trivial complexity. For example, can we show that properties whose associated boolean function family has linear decision tree complexity are hard?

  • 1
    $\begingroup$ In Rice's Theorem, the key is that the only properties allowed are properties of the language L(M), rather than the machine M (yet a description of M is the input to the problem). An analog for succinct graph problems would be something like: properties that only depend on the isomorphism type of the graph. $\endgroup$ – Joshua Grochow Nov 5 '13 at 18:50
  • $\begingroup$ @JoshuaGrochow sounds like a very good idea. It also relates to my decision tree complexity intuition (that properties with linear decision tree complexity are hard) via the evasiveness conjecture, at least for monotone properties. $\endgroup$ – Sasho Nikolov Nov 5 '13 at 19:19

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.