---
source_url: https://arxiv.org/abs/2602.20415
source_title: "Markets are competitive if and only if P != NP"
source_site: "arXiv.org"
hero_image: https://static.arxiv.org/icons/twitter/arxiv-logo-twitter-square.png
tags: computational-complexity,game-theory,market-competition
generated_at: 2026-07-03T16:01:05.946Z
model: claude-haiku-4-5
---
# 市場競争はP≠NPであることと必要十分条件—新論文が証明

競争市場の成立と計算量理論の未解決問題「P対NP問題」に直結する関係を示す論文がarXiv.orgに提出された。研究者はP≠NPが競争市場の必要条件であることを証明し、情報効率性と競争性の両立が根本的に不可能であることを示した。

Philip Mayminによる論文によると、もしP=NPであれば、企業は複雑で雑音を含む市場で協調協定からの逸脱を識別し、談合を持続可能な均衡にすることができるという。一方、P≠NPである場合、市場の需要構造に関する自然なインスタンス困難条件を満たす市場では、談合検知問題は計算量的に実行不可能となり、処罰の脅威は信頼できなくなり談合は不安定化する。

## 理論的枠組み

本論文（2026年2月23日提出、31ページ）は、Mayminの2011年研究と組み合わせて基本的な不可能性を導き出す。2011年の研究は市場効率性がP=NPを要求することを証明していた。新論文はこれに対して、競争市場の成立にはP≠NPが必要であることを示し、両者の要件が相反することを明らかにした。つまり市場は情報効率的であるか競争的であるか、どちらかのみが可能であり両立しない。

*この記事は元記事の事実のみに基づいて自動生成されました。*

## 出典
arXiv.org「Markets are competitive if and only if P != NP」https://arxiv.org/abs/2602.20415（Maymin (2011) の研究による）