問題が NP 完全であるためには、それがクラス NP に属している必要があり、それを NP 完全問題に還元するための多項式時間アルゴリズムが存在する必要があります。
ここで、reduction に指数時間アルゴリズムしかない場合はどうなるでしょうか。この問題はまだ NP-complete と呼ばれますか? それとも、そのような既存の問題はありませんか？
EDIT：また、そのような問題があるかどうか教えてください。もしあれば、それはどのクラスに属しますか？
質問する
972 次
4 に答える
4
他のNP問題が多項式時間でそれに還元できる場合にのみ、NP完全と見なすことができます。これが有用な定義である理由は、1 つの多項式時間アルゴリズムを見つけると、すべての NP 問題に対して自動的に 1 つを与えるからです。指数関数的な時間の削減を許可しても、削減された問題の多項式時間の解が見つかった場合、実際には、削減した問題を解決するのに役立ちません。
お役に立てれば。
于 2013-02-09T15:58:52.340 に答える
1
Are such problems NP-complete?
No. Proof:
Let your problem = A.
Let the NP-complete problem it reduces to in (at least) exponential time = B. "At least" because you can do extra trivial work to get to exponential time, or follow a less-than-optimal approach (to prove that there doesn't exist a more efficient reduction strategy is probably quite difficult, probably in the same ball-park as N != NP, which, to date, hasn't been solved).
Since B is NP-complete, "every problem in NP is reducible to B in polynomial time".
If A is in NP then it must be polynomial-time reducible to B. But it isn't, so it isn't in NP.
Thus it can't be NP-complete.
Put more simply - any problem in NP needs to be at most as hard as A and it clearly isn't.
Are there such problems?
I'm thinking this may be such a problem: (recursive knapsack) (I wouldn't mind a comment or two as to whether it is by someone smart)
Given a set of items, each with a weight and a value, find a subset with maximum total weight A, and also find the subset within this subset with some maximum total weight C, with the goal to maximize the sum of values of the two subsets.
To which class does it belong?
I'm pretty sure there isn't a name specifically for these, but I think many (or all?) of them are NP-hard. Proof: (at least for the above problem, assuming it is such a problem)
Let's assume the above example is such a problem and let it = H. So assume we have an oracle that can solve the above in constant time. But the knapsack problem is simply a special case of the above (C = 0), thus we can solve the knapsack problem in constant time (which is polynomial time) using the oracle.
Not sure about proving it generically. But any given problem could possibly be solved by reducing the given problem to the above problem or by reducing the problem the given problem reduces to to the knapsack problem.
EDIT: Oh, it looks like they may indeed have a name, 2-EXPTIME.
于 2013-02-09T19:11:18.033 に答える
0
複雑性理論における完全性は、特定の種類の還元に対して常に定義されますが、文脈からわかることもあり、明示的に言及されていません。NP完全問題の有名なクラスは、Richard Rastによる回答で与えられた理由により、多項式の時間削減に対して完全であると定義されています。
EXPTIME 削減のための NP 完全問題のクラスを定義できますが、このクラスはあまり興味深いものではありません。リダクションが指数時間で許容される場合、元の問題を完全に解決し、ターゲットの問題の自明なインスタンスを生成できます。これは、NP のすべての問題が、そのようなタイプの還元によって他のすべての問題に還元可能であることを意味します。
短いバージョン: リダクションは、リダクションされる問題のクラスよりも (少なくともおそらく) 弱い場合にのみ興味深いものです。
于 2013-02-09T20:54:12.027 に答える
0
何度も指摘されているように、あなたの質問の方向性は間違っています。問題Aは、NPのすべての問題Bが多項式時間で問題Aに還元できる場合、定義によりNP完全です。したがって、あなたの質問は、その還元が指数時間ではなく多項式でなければならないかどうかだと思います。
指数関数的な時間短縮を許可した場合: 次の決定問題 X を取ります: 「入力は YES ですか?」これは、考えられる最も単純な意思決定の問題です。入力が YES の場合、答えは YES です。入力が YES でない場合、答えは NO です。しかし、NP のすべての問題は、指数時間で問題 X に還元できます。確かに、問題 X を「NP 完全」と呼びたくありません。したがって、指数関数的な時間の短縮は許可されません。これを許可すると、「NP 完全」という用語がまったく無意味になるからです。
于 2014-03-22T23:29:12.670 に答える