Succinct Problems in $\mathsf{P}$

Question

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! :))

Answer 1

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)

Answer 2

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.

Answer 3

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?