<p>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 <a href="http://en.wikipedia.org/wiki/Rice%27s_theorem" rel="nofollow noreferrer">Rice’s theorem</a>.  Alas, <a href="https://cstheory.stackexchange.com/questions/668/is-there-a-complexity-theory-analogue-of-rices-theorem-in-computability-theory">finding the most general complexity-theoretic analog of Rice’s theorem is an open problem</a>, although there are results which give some forms of such complexity-theoretic analogs.</p>

CC BY-SA 3.0
2012-02-22T09:36:59.863Z
Thanks for the pointer! That was a great answer by Russell on the question you linked!
Nikhil
CC BY-SA 3.0
2012-02-22T00:46:23.403Z
2012-02-22T00:46:23.403Z
2017-04-13T12:32:28.117Z
Tsuyoshi Ito
<p>I didn't mean this to be an answer but it would require too many comments. Hope it's useful.</p>

<p>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?</p>

<p>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 <a href="http://onlinelibrary.wiley.com/doi/10.1002/1521-3870%28200010%2946:4%3C489%3a%3aAID-MALQ489%3E3.0.CO;2-F/abstract">paper</a> which shows that all such problems are UP-hard. </p>

<p>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?</p>

CC BY-SA 3.0
2013-11-05T18:50:13.097Z
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.
Joshua Grochow
CC BY-SA 3.0
2013-11-05T19:19:31.920Z
@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.
Sasho Nikolov
CC BY-SA 3.0
2012-02-23T04:02:02.247Z
2012-02-23T07:28:09.323Z
2012-02-23T07:28:09.323Z
Sasho Nikolov
<p>Here is an interesting problem whose succinct version has interesting properties. Define Circuit-Size-$2^{n/2}$ to be the problem: <em>given a Boolean function as a $2^n$-bit string, does this function have a circuit of size at most $2^{n/2}$?</em>  Note this problem is in $NP$.</p>

<p>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$.</p>

<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$. </p>

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

CC BY-SA 3.0
2012-03-07T04:11:16.637Z
this is very nice, and tears apart any intuition i thought i had..
Sasho Nikolov
CC BY-SA 3.0
2012-03-06T08:11:18.233Z
2012-03-06T08:11:18.233Z
Ryan Williams
<p>The study of Succinct representation of graphs was initiated by <a href="http://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/GW84/GW84.pdf" rel="noreferrer">Galperin and Wigderson</a> 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. <a href="http://perso.ens-lyon.fr/natacha.portier/papers/PY86.pdf" rel="noreferrer">Papadimitriou and Yanakkakis</a> 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. </p>

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

CC BY-SA 3.0
2012-02-21T18:53:41.160Z
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?
Sasho Nikolov
CC BY-SA 3.0
2012-02-21T19:51:49.133Z
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.)
Bruno
CC BY-SA 3.0
2012-02-21T19:56:06.537Z
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.
Bruno
CC BY-SA 3.0
2012-02-21T20:14:34.060Z
@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.
Nikhil
CC BY-SA 3.0
2012-02-21T20:18:08.157Z
@Bruno I was thinking on the same lines, but I couldn't immediately come up with a concrete example yet!
Nikhil
CC BY-SA 3.0
2012-02-22T01:00:20.500Z
@Bruno, sublinear time classes are very sensitive to model, arguably the right model for them should have random access to the input in which case the result you mentioned doesn't hold (ps: I am guessing you mean constant-space = real-time = Reg and not constant-time = Fin).
Kaveh
CC BY-SA 3.0
2012-02-22T08:16:01.993Z
@Kaveh, I really wanted to speak about constant-time. I don't see what you mean by "constant-time = Fin". If we consider the TM model (though I agree it's not the appropriate model for sublinear time computations, but was the model I was thinking about in my comment), the set of binary words beginning with some fixed pattern can be decided in constant-time even-though it is not finite. And sublinear-time implies constant-time since you cannot even know the length of your input. Am I wrong here?
Bruno
CC BY-SA 3.0
2012-02-22T08:18:56.347Z
@Bruno, you are right. It is $B(Fin)$, the Boolean closure of Fin.
Kaveh
CC BY-SA 3.0
2012-02-22T09:27:53.573Z
@Bruno I don't understand your comment about sublinear-time implies constant time. On the lines of your fixed pattern problem, consider this problem where the fixed pattern is of length some $n^{\epsilon}$ for $\epsilon < 1$. An algorithm solving this problem, would just query the $n^{\epsilon}$ positions for the pattern sequentially and give a correct answer, but not constant time right? Btw, wha is B(Fin)?
Nikhil
CC BY-SA 3.0
2012-02-22T13:01:31.280Z
@Nikhil What does it mean to find a fixed pattern of size $n^\epsilon$? I guess you mean that you give a family of prefixes, one for each input length, and ask whether an input of length $n$ begins with the corresponding prefix. But then you cannot test the length of your input, thus you don't know what prefix to test. I recall that I have in mind the classical Turing Machine model, and Kaveh was right to mention that it is not the appropriate model here.
Bruno
CC BY-SA 3.0
2012-02-23T06:24:28.413Z
@Bruno Of course, you are right! That was very silly of me to not consider estimating the length part.
Nikhil
<cc.complexity-theory><reference-request><complexity-classes>
Succinct Problems in $\mathsf{P}$
Nikhil
# Succinct Problems in $\mathsf{P}$

(Asked by: username_0 on 2012-02-21)

The study of Succinct representation of graphs was initiated by [Galperin and Wigderson](http://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/GW84/GW84.pdf) 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](http://perso.ens-lyon.fr/natacha.portier/papers/PY86.pdf) 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! :))

**Tags:** cc.complexity-theory, reference-request, complexity-classes
> **Comments:**
> **username_1**: 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?  
> **username_2**: 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.)  
> **username_2**: 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.  
> **username_0**: @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.  
> **username_0**: @Bruno I was thinking on the same lines, but I couldn't immediately come up with a concrete example yet!  
> **username_3**: @Bruno, sublinear time classes are very sensitive to model, arguably the right model for them should have random access to the input in which case the result you mentioned doesn't hold (ps: I am guessing you mean constant-space = real-time = Reg and not constant-time = Fin).  
> **username_2**: @Kaveh, I really wanted to speak about constant-time. I don't see what you mean by "constant-time = Fin". If we consider the TM model (though I agree it's not the appropriate model for sublinear time computations, but was the model I was thinking about in my comment), the set of binary words beginning with some fixed pattern can be decided in constant-time even-though it is not finite. And sublinear-time implies constant-time since you cannot even know the length of your input. Am I wrong here?  
> **username_3**: @Bruno, you are right. It is $B(Fin)$, the Boolean closure of Fin.  
> **username_0**: @Bruno I don't understand your comment about sublinear-time implies constant time. On the lines of your fixed pattern problem, consider this problem where the fixed pattern is of length some $n^{\epsilon}$ for $\epsilon < 1$. An algorithm solving this problem, would just query the $n^{\epsilon}$ positions for the pattern sequentially and give a correct answer, but not constant time right? Btw, wha is B(Fin)?  
> **username_2**: @Nikhil What does it mean to find a fixed pattern of size $n^\epsilon$? I guess you mean that you give a family of prefixes, one for each input length, and ask whether an input of length $n$ begins with the corresponding prefix. But then you cannot test the length of your input, thus you don't know what prefix to test. I recall that I have in mind the classical Turing Machine model, and Kaveh was right to mention that it is not the appropriate model here.  
> **username_0**: @Bruno Of course, you are right! That was very silly of me to not consider estimating the length part.  

---

## 3 answers

### Answer by username_6 on 2012-03-06. Score: 17 | Accepted answer

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)

> **Comments:**
> **username_1**: this is very nice, and tears apart any intuition i thought i had..  

---

### Answer by username_4 on 2012-02-22. Score: 12

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](http://en.wikipedia.org/wiki/Rice%27s_theorem). Alas, [finding the most general complexity-theoretic analog of Rice’s theorem is an open problem](https://cstheory.stackexchange.com/questions/668/is-there-a-complexity-theory-analogue-of-rices-theorem-in-computability-theory), although there are results which give some forms of such complexity-theoretic analogs.

> **Comments:**
> **username_0**: Thanks for the pointer! That was a great answer by Russell on the question you linked!  

---

### Answer by username_1 on 2012-02-23. Score: 9

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](http://onlinelibrary.wiley.com/doi/10.1002/1521-3870%28200010%2946:4%3C489%3a%3aAID-MALQ489%3E3.0.CO;2-F/abstract) 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?

> **Comments:**
> **username_5**: 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.  
> **username_1**: @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.  

---

