He has sent me that link to the paper this summer. Unfortunately, I had no time to read it carefully. Even if it is buggy, some technical results are quite interesting. He is in academia.

I've read Razborovs paper long ago. It is o.k. Albeit somewhat complicated. About inclusion: many important things remain outside (don't wanted to end with 1200 pages). My book is mined as a survey, not as an encyclopedy.

I now think the answer to my question is YES: n^3 edges are necessary. The reason: all-pairs shortest paths problem requires (Min,+) circuits with about n^3 gates. A related problem CONN (graph connectivity) also requires monotone boolean circuits with n^3 gates. Now, if a DAG represents K_n, then remove all labels s-->i and i-->t for i=1,...,n, ad what remains is a DAG which represents simple paths between any two vertices i,j in [n].

P.S. A DAG representing K_n can be viewed as solving the s-t shortest path problem: sum weights (labels) along the paths, and take their minimum. This is a special case of (Min,+) circuits where the +-gate is restricted: one input must be an input variable (not another gate).

P.P.S. I am sorry in advance if I will not replay for some time. Yesterday I fetched a virus to my PC, and no .EXE file works since then. I cannot even restore windows to some earlier point: regedit.exe also does not work. I am still trying.

(Virus is dead!) But my "reduction" to all-pairs shortest paths does not quite work. For every pair of vertices i,j of K_n we need the same pair u,v of source-target nodes in the DAG. Not clear how to achieve this by not expoding the number of edges in the DAG. So, my question remains still open.

hi .. death to viruses .. yes I noticed a strong resemblance of your problem to monotone circuits & was musing on that.

- new thought. you allow unlabelled edges in the DAG. why is that? I didnt follow how that relates to the overall problem. is there a proof that they are necessary or unnecessary? I think thats a good pivot place to start.

- you say that circuits are too hard to work on, but your problem shares in common being a question on minimal DAGs. and that seems to be the real difficulty at the heart of what I call "extremal circuit theory" .. DAGs! DAGs are very hard to work with. an idea from the razborov proof-- is there some way to normalize the DAG? a DAG with only two gate types seems to be able to be normalized using what in EE is called the SSR "standard simplification rule'...

- so I am skeptical of the razborov impossibility proof of approximations working to solve P!=NP because (1) it is rarely elaborated on or discussed at length by later authors, or perhaps not at all, in strong contrast to eg Natural Proofs (2) to me approximations is basically just a (quite natural) method of induction on DAGs.. so I suspect a P!=NP proof would very much resemble approximation proofs in some key ways..

- to be clearer: the supposed barrier seems to me to be a "bogeyman".. re Liptons blog "whos afraid of natural proofs"

- reduction to all pairs shortest paths-- surely the right track.. havent seen it, is that in your book? what section? is the + operator used to sum the path weights?

On "why unlabeled edges": they allow the DAG be smaller. See, e.g. the DAG of Bellman-Ford (in my post). With such edges, we can represent paths in K_n of any length uniformly: once we have a paths with k edges represented, we can keep them via unlabeled edges till the target node. But I agree, the need of such edges should be proved.

On approximations: this measures the "amount of errors". If these are "monotonically collected - everything works. But just one next NOT gate changes the world: "wrong" answers turn to correct, and vice verse. If approximation, then it must be non-monotone.

Yes, "DAGs are very hard to work with", if we want to prove that something is impossible to represent as small DAGs. This, however, happens only if edges or nodes of DAGs can do some job: test whether x_i=0 or x_i=1 (as in branching programs) , or compute AND or OR (as in circuits). My question is simpler, is "free" from these features.

"is the + operator used to sum the path weights?" YES, we sum the weights of every path, and take their minimum. This stuff is not in my book. But, as I said, my "reduction" is buggy: we need one pair of source-target nodes for all simple paths between any two vertices in K_n.

P.S. I mean "one source-target pair for each collection of simple paths between any two vertices in K_n."

P.P.S. On why "Razborovs sentence of depth for approximation method was not elaborated further". Just because it stays as it is! B.t.w. he also pointed a way to modify the approach so that it can work for general circuits as well (introduction of auxiliary variables - similar to the situation with polytopes for TSP). But this line turned to be hard to pursue.

people are very interested in reasons for why P=?NP is hard, therefore the natural proofs paper is semifamous and won an award for razborov, many citations, and much further research building on it. there is no corresponding fanfare or "reactions" over his results in barriers in monotone circuits... now of course thats merely circumstantial evidence, but I pay attn to that in this case...

in other words, still a significant and noteworthy result, but narrow...

ps watched some dijkstra vs bellman ford animations on youtube yesterday. it seems to be they are quite similar and dijkstra algorithm works counting "up" from s-node and bellman ford algorithm works counting "down" from t-node. ie some kind of symmetry between the two algorithms. this has probably been remarked on somewhere...

re monotone functions-- yes I agree they are not very powerful in some way except for slice functions. moreover, razborov has said, as far as I can tell, nothing in any of his research about slice functions!

Both algorithms have the same recursive relation. The difference: Dijkstra waits until the values of subproblems are computed (mark as "visted", keep "tempral values"), Bellman-Ford just puts this "waiting" into a DAG.

Slice functions is a different game. This is just kidding. Find a situation where negations cannot help - and you are in the world of general circuits. Graph complexity is a similar "lie": things get not simpler if one shows that negations cannot help. Than non-monocity (switching forth and back) cannot help. The lack of undertanding of a global (not step-by-step) progress in computations - this is our shrotcome.

when razborov comes up with an impossibility proof for slice fns, maybe then its time to abandon them :p ... until then, if you ask me, a P!=NP proof is hiding inside them... intending to write up my notes on that soon for my blog...

Actually, I am not focused on P!=NP. Let this game play for others. P/poly is a very hard guy. We have much weaker guyes whom we cannot fight with. My favorite: prove an exponential lower bound for read-once NBP. This is a DAG such that every s-t path is either inconsistent (makes contradictory tests x_i=0 and x_i=1 on the same variable), or is read-once (no variable is tested more than once). No progress even here in 20 years!

no answer on P vs NP in 40 yrs. but how do you really know its harder than your problem? sometimes if you knock over the big guy 1st the small guys all quickly fall in line.. =)

P.S. This is said in Sect. 16.3 of my book. "Natrural proof" say that we cannot do much better by analizing the "step-by-step" progress.

No, no: my problem is much easier (I bet 99%). And this is why I think on it.

new idea: think one needs to write out both bellman ford and dijskra as a recursive function in 'n' that is evaluating subproblems with n-1 nodes in them and taking the min of the results of the subproblems. have you seen that written out like that?

your DP formula for bellman-ford at end of the question is close, but would like to see it written as a formula computed over a graph....

On Dijkstra as a DP see this. The graph for Bellman-Ford comes after you take f_k(i) as vertices.

Sorry, the right link is this.

Actually, the recursive relation of both algorithms is the same. The point: BF resolves it in a "fair" manner (first paths with k edges, then with k+1). Dijkstra works in a cyclic graph. So, he first declares vertices as "visited", then as "marked". The realization of his recursion requires comarisions between values already computed, whereas BF does not need this. Hence, BF is much simpler.

looking at the paper, thx... these algorithms also remind me of the minimum spanning tree algorithm....

eq (4) in the paper is the same as yours at end of question? "It should be stressed, here and elsewhere, that the DP functional equation does not constitute an algorithm"

so what does the recursive algorithm for bellman-ford look like? it would be interesting to write down the recursive algorithm for each problem and compare them...

note of course that recursion in algorithms and induction on problems often overlap & become the same thing...