StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<pre><code>Are such problems NP-complete? </code></pre> <p>No. Proof:</p> <p>Let your problem = A.</p> <p>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).</p> <p>Since B is NP-complete, <a href="http://en.wikipedia.org/wiki/NP-complete#Formal_definition_of_NP-completeness" rel="nofollow">"every problem in NP is reducible to B in polynomial time"</a>.</p> <p>If A is in NP then it must be polynomial-time reducible to B. But it isn't, so it isn't in NP.</p> <p>Thus it can't be NP-complete.</p> <p>Put more simply - any problem in NP needs to be at most as hard as A and it clearly isn't.</p> <pre><code>Are there such problems? </code></pre> <p>I'm thinking this <strong>may</strong> be such a problem: (recursive <a href="http://en.wikipedia.org/wiki/Knapsack_problem" rel="nofollow">knapsack</a>) (I wouldn't mind a comment or two as to whether it is by someone smart)</p> <p>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.</p> <pre><code>To which class does it belong? </code></pre> <p>I'm pretty sure there isn't a name specifically for these, but I think many (or all?) of them are <a href="http://en.wikipedia.org/wiki/NP-hard" rel="nofollow">NP-hard</a>. Proof: (at least for the above problem, assuming it is such a problem)</p> <p>Definition: <a href="http://en.wikipedia.org/wiki/NP-hard" rel="nofollow">"A problem H is NP-hard if ... (an NP-complete problem) L can be solved in polynomial time by an oracle machine with an oracle for H"</a>.</p> <p>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.</p> <p>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.</p> <p><strong>EDIT:</strong> Oh, it looks like they may indeed have a name, <a href="http://en.wikipedia.org/wiki/2-EXPTIME" rel="nofollow">2-EXPTIME</a>.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload