The Idea of Not Aiming Directly at the NP Problem Itself
When it comes to the P vs NP problem, I think it’s best not to try to solve the problem itself directly. This is a prize-bearing unsolved problem — the kind of question that top experts around the world have been struggling with for decades and still haven’t cracked. So before even mentioning limited resources, we should accept the fact that even with unlimited resources, we wouldn’t be able to solve it ourselves.
So what should we do instead? We narrow our scope — like looking through a microscope. For example, there are problems like SVP (Shortest Vector Problem) and CVP (Closest Vector Problem), which are already known to be NP-complete or NP-related. Starting from there, we can look at algorithms that currently solve them in exponential time and ask: can we make those exponential-time algorithms more efficient? That’s a good direction to pursue.
The Hierarchy of Computational Complexity and Focusing the Scope
When we say “exponential time,” that phrase actually covers a range of hierarchies. Even within exponential time, there are relatively lighter and heavier layers. In the sense of Bourbaki’s mathematical hierarchy, you could call these “comparative levels.” Naturally, from the viewpoint of computational complexity, the lower the level, the better.
Therefore, even within that scope, aiming for a lower layer — something modest but practical and approachable — makes sense. The same reasoning applies to CVP and similar problems.
The Nature of NP-Complete Problems and a Realistic Approach
Each NP-complete problem has its own internal structure, so even if we focus only on CVP, finding an algorithm that solves it in a lower complexity class would have implications for all other NP-complete problems. That interconnection is both the power and the difficulty of NP-complete problems.
So realistically, instead of going after something as huge as the P vs NP problem itself, it’s much more productive to focus on smaller, more concrete scopes of inquiry.
The Value of Starting Small
I also started with small problems. It was only by coincidence that one of them turned out to yield a somewhat bigger result — pure luck, really. So at the beginning, it’s completely fine to tackle something modest, even unglamorous. It doesn’t have to stand out; what matters is that it has novelty.
For example, you might take an existing algorithm that runs in exponential time and see if it can be made more efficient — even slightly. It’s theoretical work, yes, but engaging with that kind of “subtle but genuinely valuable” area is important, I think.
Interest in NP but Not NP-Complete Problems
Another point: NP-complete problems tend to attract all the attention, but there also exist problems that belong to the NP class without being NP-complete. Theoretically, such problems are considered essentially simpler. Constructing and solving one of these — or designing an algorithm for it — could also be very interesting.
If we only fixate on NP-complete problems, our perspective becomes too skewed toward pure theory. That’s why I believe it’s important to return to the foundation — to the evaluation of computational complexity itself.
Returning to the Foundations of Complexity Evaluation
After all, the entire discussion around P vs NP originated from the study of computational complexity. So we should ask again: how do we evaluate computational complexity? Measuring complexity isn’t about elapsed time; it’s about counting the number of operations — additions, subtractions, multiplications, and divisions. Starting once again from that fundamental level might be the right approach.
NP問題そのものを狙わないという考え方
PNP問題というのは、そのものを直接解こうとしない方がいいと思います。これはもう賞金付きの未解決問題で、世界中のプロが挑んでも解けていない問題です。リソースが限られているとかそういう話以前に、リソースが無限にあっても我々には解けないということをまず理解すべきです。
ではどうするかというと、もっと射程を狭めるんです。顕微鏡で覗くように。例えばSVPやCVPといった問題がありますが、これらがNPコンプリート、もしくはNP関連の問題であることはすでにわかっています。そこから出発して、たとえば指数関数時間で解けるとした場合、その指数関数時間のアルゴリズムをより効率化できないかに注目する、という方向性です。
計算量の階層構造と射程の絞り方
「指数関数時間」と一口に言っても、実際にはいろいろな階層があり、同じ指数関数時間でもその中に比較的軽い階層と重い階層があります。ブルバキ的な観点で言えば「比較の階層」と呼ばれるようなものですね。当然、計算量的にはより低い階層の方が優れています。
したがって、その中でもなるべく低いものを目指すとか、そういう地味ではあるけれど実用的で取り掛かりやすい方向に射程を狭めた方が良い。CVPについても同様です。
NP完全問題の本質と現実的アプローチ
NP完全問題というのは内部構造がそれぞれ違うため、CVPだけに注目しても、それをより低い階層で解けるアルゴリズムが見つかれば、他のNP完全問題にも波及してしまいます。そこがNP完全問題の強みでもあり、難しさでもあります。
ですから、現実的なアプローチとしては、あまりに大きな問題（つまりPNPそのもの）を狙わず、もっと小さな射程で具体的に考えることが重要だと思います。
小さな問題から始める意義
私自身最初は小さな問題から取り組みました。たまたまそこで少し大きめの成果が出ただけで、結果論です。最初は本当に地味で構いません。目立たなくてもいい。ただ、新規性があれば十分です。
たとえば、既知のアルゴリズムの中で、指数関数時間のものをより効率的にできないかとか、少しでも改良できるかという方向。セオリ的ではありますが、そうした「地味だけど確実に価値のある」領域に取り組むことが大事だと思います。
NP完全でないNP問題への関心
また、NP完全な問題ばかりが注目されがちですが、クラスNPに属しながらNP完全でない問題もあります。そうした問題は理論的には「エッセンシャルに簡単な問題」と見なされます。もしそういう問題を一つ構築し、解いてみる、あるいはアルゴリズムを考えてみるというのも面白いと思います。
NP完全問題ばかりに偏ると、どうしても理論的方向に寄りすぎてしまいますから、もう少し「計算量の評価」という原点に戻ることが大切です。
計算量の評価の出発点
PNPの議論も、もともとは計算量の評価から出発したものです。では「計算量をどうやって評価するのか？」という問いに立ち返る。計算量を測るとはつまり、時間ではなく、演算の回数──足し算、引き算、掛け算、割り算などの回数を数えることです。そうした基本から改めて取り組んでみるのが良いと思います。