两个拟阵公共基的近似计数

两个拟阵公共基的近似计数

Approximate counting of common bases of two matroids

OpenAI 数学仓库收录的研究手稿。展开查看英文摘要，或标记后让我进一步解释。

具体内容

稿件研究在独立预言机访问下计数两个同秩任意拟阵的公共基。作者声称给出完全多项式随机近似方案（FPRAS），算法不需要任一拟阵的显式表示，且每次执行的预言机调用次数与位运算量均有多项式界。该问题属于组合计数与近似算法的交叉方向，若成立可为拟阵交计数提供通用近似工具，但作为AI产生的研究手稿，尚未经独立审查或同行评议。

• 研究两个同秩任意拟阵公共基的计数问题
• 作者声称给出完全多项式随机近似方案，仅需独立预言机
• 预言机调用与位运算量在每次执行中均有多项式界

AI 产生的研究手稿；收录不表示已完成独立审查或同行评议。

英文原始摘要

We give a fully polynomial randomized approximation scheme for counting the common bases of two arbitrary matroids of the same rank, supplied by independence oracles. The algorithm requires no explicit representation of either matroid and has polynomial bounds on both oracle calls and bit operations on every execution.

用户标记：未标记

固定编号：561fc655156dffc6