<p>One result of this kind was proved by Lipton <a href="http://www.cs.umd.edu/~gasarch/ramsey/lipton.pdf">"On proving that a graph has no large clique: A connection with Ramsey theory"</a>. He connects lower bound conjectures with purely graph theoretic results, showing that if $NP$ is not contained in $coNTIME(n^{O(\log n)})/(\log \log n)$, then the inapproximability of $MAX-CLIQUE$ implies that there are graphs with neat Ramsey-theoretic properties. (See the paper for definitions.) I have no idea if any progress has been made on proving whether or not such graphs actually exist. </p>

CC BY-SA 2.5
2010-09-16T15:34:07.493Z
I dont want to start another question while this is still going, but I would be very interested in additional results that connect graph Ramsey theory to computational complexity, if anyone knows of any.
Aaron Sterling
CC BY-SA 2.5
2010-09-16T15:39:09.730Z
One place to start looking: http://www.cs.umd.edu/~gasarch/ramsey/
Ryan Williams
CC BY-SA 2.5
2010-09-16T15:17:27.183Z
2010-09-16T15:17:27.183Z
Ryan Williams
<p>Sorry, I came across this 1 year old question only now ...</p>

<p>In fact, there are lots of results showing that explicit graphs with some properties imply strong lower bounds for boolean functions. Say, graphs of high affine or projective dimension imply strong lower bounds for formulas and branching programs. There are also "simpler" measures of graphs, good lower bounds on which would have great consequences in computational complexity. Let me sketch some of them.</p>

<p>View graphs as sets of edges. Let $s(G)$ be the smallest number $s$ such that $G$ can be written as an intersection of $\leq s$ graphs, each of which is a union of $\leq s$ bicliques (bipartite complete graphs). Easy counting shows that $s(G)\geq n^{1/2}$ for almost all bipartite $n\times n$ graphs. But by Valiant's results, every explicit bipartite graph $G$ (more exactly, a sequence of graphs) with $s(G)\geq n^c$ for a constant $c&gt;0$ would resolve an old problem: would give a boolean function which cannot be computed by a log-depth circuit of linear size.  It is conjectured that dense graphs without $K_{2,2}$ have large $s(G)$.</p>

<p>Even better, let $Star(G)$ be the smallest number of fanin-$2$ union and intersection operations that are enough to generate $G$ starting with complete stars (graphs of the type $K_{1,n}$ or $K_{n,1}$). Counting shows that most of the graphs have $Star(G)=\Omega(n^2/\log n)$. But any $G$ with $Star(G)\geq (4+c)n$ for a constant $c&gt;0$ would give an explicit boolean function requiring circuits of exponential size! If the graph has dimension $m\times n$ with $m=o(n)$, then even a lower bound $Star(G)\geq (2+c)n$ would have the same consequences. The best we can show so far is $Star(G)\geq 2n-1$.   </p>

<p>Let $Sym(G)$ be the smallest number $t$ for which there exists a subset $T\subseteq\{0,1,\ldots,t\}$ and a sequence of $t$ bicliques such that $(u,v)\in G$ iff the number of bicliques containing $(u,v)$ belongs to $T$. Again, counting gives $Sym(G)\geq n/2$ for most of the graphs. But by results of Yao, Beigel and Tarui any explicit graph with $Sym(G)$ larger than  $2^{poly(\ln\ln n)}$ would give us a boolean function outside $ACC$. Warning: being "combinatorialy complicated" alone does not imply large $Sym(G)$: there exists strongly Ramsey graphs for which $Sym(G)=O(\log n)$, even if $T$ = set of odd integers.</p>

<p>More details on how all this happens can be found <a href="http://www.thi.informatik.uni-frankfurt.de/~jukna/boolean/index.html">here</a>.</p>

CC BY-SA 3.0
2011-10-12T16:28:51.993Z
this is very neat.
Suresh Venkat
CC BY-SA 3.0
2011-10-12T14:06:05.570Z
2011-10-12T14:06:05.570Z
Stasys
<p>A classical example was by Valiant (I don't know the reference but I think this is described in the book of <a href="http://www.math.ias.edu/~avi/BOOKS/expanderbookr1.pdf" rel="nofollow">Hoory, Linial and Wigderson on expander graphs</a>). Valiant showed an explicit lower bound (I think that a certain explicit function $f:{0,1}^n\rightarrow {0,1}^n$ doesn't have a circuit of $O(n)$ size and $O(\log n)$ depth - something we're still far from proving) under the assumptions that certain types of graphs, called superconcentrators, don't exist. (This was an asymptotic question, and not about just one graph.) However he later showed that these do exist (and in fact have other uses)</p>

CC BY-SA 2.5
2010-09-19T02:20:42.853Z
2010-09-19T02:20:42.853Z
Boaz Barak
<p>The answer is certainly "yes" if we talk about families of graphs, rather than specific graphs.  For example, there's a conjecture of Mihail and Vazirani that all 0/1 polytopal graphs are either good or very good edge expanders (ie, that their edge expansion is bounded below by 1/polynomial(degree), or 1).  </p>

<p>If this is true, then there exist efficient randomized Markov chain Monte Carlo approximation algorithms for a number of open combinatorial and counting problems via a sampling strategy of Alon, Jerrum, and Sinclair. </p>

<p>In a similar vein, if there exist families of polytopal graphs whose diameter grows faster than any polynomial in the number of facets and graph degree, then linear programming cannot be solved in strongly polynomial time via edge-following algorithms.</p>

CC BY-SA 2.5
2010-09-16T07:36:09.590Z
2010-09-16T07:36:09.590Z
Anand Kulkarni
<p>Expanding on Anand Kulkarni's comment:</p>

<p>Suppose there is a deterministic Turing machine M that recognizes SAT in polynomial time.  Then the finite transition relation of M will be a function.  We know of TMs that recognize SAT in polynomial time, but their transition relations are not functions.  Note that the transition relation is a bipartite directed graph with tuples of (state, tape symbol) in the one bipartition, tuples of (state, tape symbol, move) in the other bipartition, and arcs from pairs to triples.</p>

<p>So trivially if there is such a digraph that is a function, then P=NP.</p>

<p>Of course, this is not a very natural definition, as it requires ancillary machinery to give meaning to the requirement that every path in the state space that reaches the accepting state has length bounded by a polynomial in the input size.  It is not at all obvious what the set of finite graphs representing polytime-bounded Turing machines looks like, or whether these graphs have interesting graph-theoretic properties.</p>

CC BY-SA 2.5
2010-09-16T13:40:45.183Z
2010-09-16T13:40:45.183Z
András Salamon
<p>Are there any known results showing that existence (or non-existence) of finite graphs with specific computable properties imply certain complexity results (such as P = NP)?</p>

<p>Here's one <strong>completely hypothetical</strong> result: If a finite graph exists with distingushed edges A, B, C and D such that all maximum matchings either contain all of A, B, C, and D, or contain none of A, B, C and D, then P = NP.</p>

CC BY-SA 2.5
2010-09-16T07:21:28.667Z
when you say finite, maybe you mean a family of graphs for different values of $n$ ? Otherwise I don't understand how a finite sized obstacle can collapse P and NP.
Suresh Venkat
CC BY-SA 2.5
2010-09-16T07:40:11.310Z
It's an even more interesting question if we ask about a single graph. None come to mind in a graph setting, but a proof of P=NP would itself be a finite object.
Anand Kulkarni
CC BY-SA 2.5
2010-09-16T07:47:17.603Z
If the question is interpreted literally, the answer is trivially yes.  Since there is an efficiently computable one-to-one correspondence between graphs and bit strings, you can encode a proof (in any fixed axiomatic system) by a graph instead of a bit string.  If a graph which encodes a proof of P=NP exists, then P=NP (as long as the axiomatic system in question is sound).  However, this answer is nonsense.
Tsuyoshi Ito
CC BY-SA 2.5
2010-09-16T07:52:57.317Z
No need for interpretation, the question is perfectly clear. I may add, It is very well motivated.
Mohammad Al-Turkistany
CC BY-SA 2.5
2010-09-16T08:08:39.293Z
Agreed on both; what we're after is a natural example rather than one obtained by artificial encodings.  Is there a single graph whose existence is known to naturally show or has been used to show a class separation / collapse?  Some places to look might be in applications of spectral graph theory or the probabilistic method, or maybe even GCT.
Anand Kulkarni
CC BY-SA 2.5
2010-09-19T02:58:39.897Z
Another hypothetical result: If a certain type of expander graph family exists, then strong derandomization is possible, and thus P = BPP and NP = MA = AM.
Robin Kothari
CC BY-SA 2.5
2010-09-23T05:08:03.480Z
If there's an algorithm for an NP-complete problem that uses polynomial p(n) number of copies of a certain graph G of constant size ( may be as subgraphs of a larger graph) and its  time complexity is polynomial in p(n)*|G|, then the existence of such a graph will imply P = NP
Ajay
<cc.complexity-theory>
Results showing existence/non-existence of finite graphs with specific computable properties imply certain complexity results
Ajay
# Results showing existence/non-existence of finite graphs with specific computable properties imply certain complexity results

(Asked by: username_0 on 2010-09-16)

Are there any known results showing that existence (or non-existence) of finite graphs with specific computable properties imply certain complexity results (such as P = NP)?

Here's one **completely hypothetical** result: If a finite graph exists with distingushed edges A, B, C and D such that all maximum matchings either contain all of A, B, C, and D, or contain none of A, B, C and D, then P = NP.

**Tags:** cc.complexity-theory

> **Comments:**
> **username_1**: when you say finite, maybe you mean a family of graphs for different values of $n$ ? Otherwise I don't understand how a finite sized obstacle can collapse P and NP.  
> **username_2**: It's an even more interesting question if we ask about a single graph. None come to mind in a graph setting, but a proof of P=NP would itself be a finite object.  
> **username_3**: If the question is interpreted literally, the answer is trivially yes.  Since there is an efficiently computable one-to-one correspondence between graphs and bit strings, you can encode a proof (in any fixed axiomatic system) by a graph instead of a bit string.  If a graph which encodes a proof of P=NP exists, then P=NP (as long as the axiomatic system in question is sound).  However, this answer is nonsense.  
> **username_4**: No need for interpretation, the question is perfectly clear. I may add, It is very well motivated.  
> **username_2**: Agreed on both; what we're after is a natural example rather than one obtained by artificial encodings.  Is there a single graph whose existence is known to naturally show or has been used to show a class separation / collapse?  Some places to look might be in applications of spectral graph theory or the probabilistic method, or maybe even GCT.  
> **username_5**: Another hypothetical result: If a certain type of expander graph family exists, then strong derandomization is possible, and thus P = BPP and NP = MA = AM.  
> **username_0**: If there's an algorithm for an NP-complete problem that uses polynomial p(n) number of copies of a certain graph G of constant size ( may be as subgraphs of a larger graph) and its  time complexity is polynomial in p(n)*|G|, then the existence of such a graph will imply P = NP  

---

## 5 answers

### Answer by username_6 on 2010-09-16. Score: 13

One result of this kind was proved by Lipton ["On proving that a graph has no large clique: A connection with Ramsey theory"](http://www.cs.umd.edu/~gasarch/ramsey/lipton.pdf). He connects lower bound conjectures with purely graph theoretic results, showing that if $NP$ is not contained in $coNTIME(n^{O(\log n)})/(\log \log n)$, then the inapproximability of $MAX-CLIQUE$ implies that there are graphs with neat Ramsey-theoretic properties. (See the paper for definitions.) I have no idea if any progress has been made on proving whether or not such graphs actually exist.

> **Comments:**
> **username_7**: I dont want to start another question while this is still going, but I would be very interested in additional results that connect graph Ramsey theory to computational complexity, if anyone knows of any.  
> **username_6**: One place to start looking: http://www.cs.umd.edu/~gasarch/ramsey/  

---

### Answer by username_8 on 2011-10-12. Score: 13

Sorry, I came across this 1 year old question only now ...

In fact, there are lots of results showing that explicit graphs with some properties imply strong lower bounds for boolean functions. Say, graphs of high affine or projective dimension imply strong lower bounds for formulas and branching programs. There are also "simpler" measures of graphs, good lower bounds on which would have great consequences in computational complexity. Let me sketch some of them.

View graphs as sets of edges. Let $s(G)$ be the smallest number $s$ such that $G$ can be written as an intersection of $\leq s$ graphs, each of which is a union of $\leq s$ bicliques (bipartite complete graphs). Easy counting shows that $s(G)\geq n^{1/2}$ for almost all bipartite $n\times n$ graphs. But by Valiant's results, every explicit bipartite graph $G$ (more exactly, a sequence of graphs) with $s(G)\geq n^c$ for a constant $c>0$ would resolve an old problem: would give a boolean function which cannot be computed by a log-depth circuit of linear size. It is conjectured that dense graphs without $K\_{2,2}$ have large $s(G)$.

Even better, let $Star(G)$ be the smallest number of fanin-$2$ union and intersection operations that are enough to generate $G$ starting with complete stars (graphs of the type $K\_{1,n}$ or $K\_{n,1}$). Counting shows that most of the graphs have $Star(G)=\Omega(n^2/\log n)$. But any $G$ with $Star(G)\geq (4+c)n$ for a constant $c>0$ would give an explicit boolean function requiring circuits of exponential size! If the graph has dimension $m\times n$ with $m=o(n)$, then even a lower bound $Star(G)\geq (2+c)n$ would have the same consequences. The best we can show so far is $Star(G)\geq 2n-1$.

Let $Sym(G)$ be the smallest number $t$ for which there exists a subset $T\subseteq\{0,1,\ldots,t\}$ and a sequence of $t$ bicliques such that $(u,v)\in G$ iff the number of bicliques containing $(u,v)$ belongs to $T$. Again, counting gives $Sym(G)\geq n/2$ for most of the graphs. But by results of Yao, Beigel and Tarui any explicit graph with $Sym(G)$ larger than $2^{poly(\ln\ln n)}$ would give us a boolean function outside $ACC$. Warning: being "combinatorialy complicated" alone does not imply large $Sym(G)$: there exists strongly Ramsey graphs for which $Sym(G)=O(\log n)$, even if $T$ = set of odd integers.

More details on how all this happens can be found [here](http://www.thi.informatik.uni-frankfurt.de/~jukna/boolean/index.html).

> **Comments:**
> **username_1**: this is very neat.  

---

### Answer by username_9 on 2010-09-19. Score: 11

A classical example was by Valiant (I don't know the reference but I think this is described in the book of [Hoory, Linial and Wigderson on expander graphs](http://www.math.ias.edu/~avi/BOOKS/expanderbookr1.pdf)). Valiant showed an explicit lower bound (I think that a certain explicit function $f:{0,1}^n\rightarrow {0,1}^n$ doesn't have a circuit of $O(n)$ size and $O(\log n)$ depth - something we're still far from proving) under the assumptions that certain types of graphs, called superconcentrators, don't exist. (This was an asymptotic question, and not about just one graph.) However he later showed that these do exist (and in fact have other uses)


---

### Answer by username_2 on 2010-09-16. Score: 5

The answer is certainly "yes" if we talk about families of graphs, rather than specific graphs. For example, there's a conjecture of Mihail and Vazirani that all 0/1 polytopal graphs are either good or very good edge expanders (ie, that their edge expansion is bounded below by 1/polynomial(degree), or 1).

If this is true, then there exist efficient randomized Markov chain Monte Carlo approximation algorithms for a number of open combinatorial and counting problems via a sampling strategy of Alon, Jerrum, and Sinclair.

In a similar vein, if there exist families of polytopal graphs whose diameter grows faster than any polynomial in the number of facets and graph degree, then linear programming cannot be solved in strongly polynomial time via edge-following algorithms.


---

### Answer by username_10 on 2010-09-16. Score: 3

Expanding on username_2's comment:

Suppose there is a deterministic Turing machine M that recognizes SAT in polynomial time. Then the finite transition relation of M will be a function. We know of TMs that recognize SAT in polynomial time, but their transition relations are not functions. Note that the transition relation is a bipartite directed graph with tuples of (state, tape symbol) in the one bipartition, tuples of (state, tape symbol, move) in the other bipartition, and arcs from pairs to triples.

So trivially if there is such a digraph that is a function, then P=NP.

Of course, this is not a very natural definition, as it requires ancillary machinery to give meaning to the requirement that every path in the state space that reaches the accepting state has length bounded by a polynomial in the input size. It is not at all obvious what the set of finite graphs representing polytime-bounded Turing machines looks like, or whether these graphs have interesting graph-theoretic properties.


---

