A lower bound technique for nondeterministic graph-driven read-once-branching programs and its applications

摘要

We present a new lower bound technique for a restricted branching program model, namely for nondeterministic graph-driven read-once branching, programs (g.d.-BPls). The technique is derived by drawing a connection between omega-nondeterministic g.d.-BP Is and omega-nondeterininistic communication complexity (for the nondeterministic acceptance modes omega is an element of {boolean OR, boolean AND, +}). We apply the technique in order to prove an exponential lower bound for integer multiplication for omega-nondeterministic well-structured g.d.-BP1s. (For omega = + an exponential lower bound was already obtained in [5] by using a different technique.) Further, we use the lower bound technique to prove for an explicitly defined function which can be represented by polynomial size omega-nondeterministic BP1s that it has exponential complexity in the omega-nondeterministic well-structured g.d.-BP1 model for omega is an element of {boolean OR, +}. This answers an open question from Brosenne et al. [7], whether the nondeterministic BP1 model is in fact more powerful than the well-structured graph-driven variant.