应用数理研究部门（牧野 和久）

About关于研究室

将离散结构运用于最优化与算法。

牧野研究室解析图论和组合论等离散结构，并研究利用这些结构的最优化与算法。
代表性研究是单调逻辑函数的对偶化问题。
已知该问题与数学规划、人工智能、数据库、分布式系统、学习理论等众多领域中出现的许多问题，在多项式时间归约的意义下是等价的。
此外还研究整数线性不等式系统、互补问题、在线优化问题、鲁棒优化、博弈论的均衡解等。

Research研究课题

该研究室研究解析图论和组合论等离散结构，以及利用这些结构的最优化与算法。主要致力于单调逻辑函数的对偶化问题，以及推理领域中逻辑假设的补全问题等。

※示意图

单调逻辑函数的对偶化问题↗

这是由给定的合取范式，求出与之等价的单调析取范式的问题。Fredman 和 Khachiyan 已证明该问题可在拟多项式时间内求解，但能否在多项式时间内求解目前仍不清楚。

※示意图

Horn推理中逻辑假设的补全↗

针对推理领域中逻辑假设的补全问题，通过合作研究推翻了此前被广泛相信的猜想，证明在最重要的类别——Horn推理中，可以在增量多项式时间内完成。

Voices学长学姐的评价

评价基于在读（或曾在读）学生的个人经历，不代表研究室官方观点。评价的有无或数量不代表对研究室的评价。

对于接受采访的学生，无论内容如何，我们可能会赠送谢礼（价值1,000日元的礼品）。