P vs NP problem

[piː vɜːrsəs ɛn piː ˈprɒbləm] ピー バーサス エヌピー プロブレム

1. 計算複雑性理論における未解決の主要な問題で、決定問題のクラスPとNPが等しいか否かを問うもの。

P vs NP問題は、コンピューターで効率的に解ける問題（クラスP）と、与えられた解が正しいかどうかの確認は効率的にできるが、解を見つけること自体は難しいと考えられている問題（クラスNP）が、本質的に同じ集合に属するのか、それとも異なるのかを問う、計算機科学における根源的な問いです。この問題は、効率的なアルゴリズムの限界や、暗号技術、人工知能、最適化問題など、多岐にわたる分野に革命的な影響をもたらす可能性がありますが、未だ解決されていません。

The P vs NP problem is one of the most significant unsolved questions in computer science. (P vs NP問題は、コンピューター科学における最も重要な未解決問題の一つです。)

• The P vs NP problem: P vs NP問題。計算複雑性理論における主要な未解決問題の一つです。
• is: 〜である、という状態や事実を表します。
• one of the most significant: 最も重要な〜の一つ、という比較級と最上級を含む表現です。
• unsolved questions: 未解決の問題。まだ答えが見つかっていない問いを指します。
• in computer science: コンピューター科学において、という分野を示します。

Solving the P vs NP problem would have profound implications for cryptography and artificial intelligence. (P vs NP問題を解決することは、暗号理論と人工知能に深遠な影響を与えるでしょう。)

• Solving: 〜を解決すること。動名詞で主語として使われています。
• the P vs NP problem: P vs NP問題。計算複雑性理論の特定の未解決問題です。
• would have: 〜を持つだろう、という仮定や推測を表します。
• profound implications: 深遠な影響。非常に重要で広範囲にわたる影響を指します。
• for cryptography and artificial intelligence: 暗号理論と人工知能にとって、という対象分野を示します。

Many researchers believe that P does not equal NP, but a formal proof is still elusive. (多くの研究者はP ≠ NPだと信じていますが、正式な証明はまだ見つかっていません。)

• Many researchers: 多くの研究者。この分野で活動する専門家を指します。
• believe that: 〜だと信じている、という意見や考えを示します。
• P does not equal NP: PはNPと等しくない。クラスPとクラスNPが異なるという主張です。
• but: しかし、という逆接を表す接続詞です。
• a formal proof: 正式な証明。厳密で論理的な検証結果を指します。
• is still elusive: まだ見つかっていない/捉えがたい、という状況を表します。

関連

• computational complexity
• NP-complete
• polynomial time
• exponential time
• algorithm
• theoretical computer science
• Clay Millennium Prize Problems