A mathematician who reviews all the new work on completeness proofs for computational processes. This blog and a few others I check into and follow the links. Behind the scenes, for me, is theory about matching two or more sequences by matching their algebraic generators. Then show a sequence if increasingly refined generators that reach a hard bound, a contained set of solutions that are compact under indefinite recursions.
Interesting stuff, like this:
Cohen’s paper. The main advance was to use a beautiful concept of trees of degree-polynomials with interlacing roots from MSS and improve it so that the requisite trees have polynomial rather than exponential maximum branch length, which governs the time of the algorithm. The paper well rewards further reading.
OK, not having followed up, but my impression is that Cohen proved, for a class of generators, that they are a well queue generating graph, polynomial time. My interpretation,"How do we know a graph is minimal? Push some queuable items thru it and see if loops show up. (Are the queues stable).
A queueable items that have stable, small queues can survive arrival errors that are within the bounds identified in the generator skewness, keeping full conservation of queuing stuff.
No comments:
Post a Comment