9
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Suresh Venkat Sep 16 '10 at 7:21
  • 2
    $\begingroup$ 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. $\endgroup$ – Anand Kulkarni Sep 16 '10 at 7:40
  • 7
    $\begingroup$ 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. $\endgroup$ – Tsuyoshi Ito Sep 16 '10 at 7:47
  • 1
    $\begingroup$ 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. $\endgroup$ – Anand Kulkarni Sep 16 '10 at 8:08
  • 1
    $\begingroup$ 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. $\endgroup$ – Robin Kothari Sep 19 '10 at 2:58
13
$\begingroup$

One result of this kind was proved by Lipton "On proving that a graph has no large clique: A connection with Ramsey theory". 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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Aaron Sterling Sep 16 '10 at 15:34
  • 3
    $\begingroup$ One place to start looking: cs.umd.edu/~gasarch/ramsey $\endgroup$ – Ryan Williams Sep 16 '10 at 15:39
13
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ this is very neat. $\endgroup$ – Suresh Venkat Oct 12 '11 at 16:28
11
$\begingroup$

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). 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)

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

Expanding on Anand Kulkarni'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.

$\endgroup$

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.