Bin Cai

Beyond Distance Ordering: Resource Complexity and Universal Optimality of Exact Labeled Directed Shortest Paths

An exact transcript-cone game yields one uniform interpreter whose charged addition-comparison cost equals one uniform interpreter whose optimal actions are synthesizable in polynomial space but may require exponential time.