0
$\begingroup$

I explain it better:
There are some algorithms that is clearly in NP, also NP-complete, but that under certain conditions they can be solved in polynomial time.

An example is Bin Packing, the decision version of the problem is an NP-complete problem and it's defined as follows in the book "Computers and Intractability" by Michael R. Garey and David S. Johnson:

INSTANCE: Finite set $U$ of items, a size $s(u) \in Z$ for each $u \in U$, a positive integer bin capacity $B$, and a positive integer $K$.
QUESTION: Is there a partition of $U$ into disjoint sets $U_1, U_2, ..., U_k$ such that the sum of sizes of the items in each $U_i$ is $B$ or less.

And there is a comment that says "Solvable in polynomial time for any fixed $B$ by exhaustive search."
I have asked in math.stackexchange how it is possible and I get a clearly answer about that:
https://math.stackexchange.com/questions/3804912/bin-packing-problem-with-fixed-size-of-bins

Now I ask you why we can't applicate things like this to all instance of the problems? What is the thing that I don't get that makes this impossible?
For example, in the Bin Packing problem I think that I would can always enumerate the solutions and search into them because the $ B $ is always fixed once I get it, ok the number of the solutions could be a huge number, but it still remains a polynomial time algorithm. Or the "enumerate solutions" meanings that they are precomputated and the algorithm just has to check between them? And in this case, why we can't precomputate always?
I'm not saying something like $ P=NP $ because I'm sure not the first person that think about this thing and if the most accredited opinion is that $ P \not= NP $ it must be why this thought of mine is wrong and I want to understand why this isn't a generic solution for the problem, and where I'm wrong.

$\endgroup$
1
  • 3
    $\begingroup$ It is similar to $f(x,y)=x2^y$ being non-linear, but producing a linear function, $g(x):x\mapsto f(x,y)$, for each specific value of $y$. $\endgroup$
    – plop
    Aug 28, 2020 at 14:50

1 Answer 1

1
$\begingroup$

It's often the case that an NP-complete problem has some parameter $b$ that when fixed to a small constant makes an polynomial algorithm possible, yes.

However in fixing $b$ that problem (at least as of writing when $P =^? NP$) loses its completeness. That means when we want to do a reduction we (for at least some instances) need this parameter to be bigger than $b$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.