Home of Mr. 5

本文继续解决【科研点子】Online Bipartite Matching with Reusable Resources中的两个Open Problem | Home of Mr. 5中遇到的问题，并提出一种可能的LP分析模式。

Online Bipartite Matching with Reusable Resources这篇文献里有两个比较重要的open problem。

1. RANKING算法在该模型下怎么分析C.R.

2. 该模型下的最佳C.R.是多少，有可能达到吗？

就我目前的、尚未验证正确性的证明来看，这两个问题的答案是：该模型下的最佳C.R.就是，而且RANKING算法就可以达到。（更新后该结果不确定是否能得到）

本文译自Existence of functions with exponential circuits complexity，原作者David Steurer。有删改。

本文所述定理由C. E. Shannon于1949年在The synthesis of two-terminal switching circuits提出。

在研究的时候鼓捣出来一些好玩的东西。

继续记录一些要用到的 prophet inequality 相关的结论。（对无相关了解者可读性低）

最近做的东西和先知不等式牵扯极多，不妨更个博客记录一下这个领域的经典结果。

如果你上一门本科阶段的计算理论课，你通常会学到“泵引理”这个证明一个语言非正则的手段。

但是，泵引理条件并非语言是正则语言的充要条件。你自然要好奇，有没有什么条件，既是充要的，又易于使用（来证明非正则性）？

最近对图论里的一些东西比较着迷，读到了下面这篇论文：

Finding Paths with Minimum Shared Edges

这篇论文提出了一个叫Minimum Shared Edges的问题，并说明了该问题的决策版本是NP-Complete的。