Computer Science – Computational Complexity
Scientific paper
2008-08-09
Computer Science
Computational Complexity
The preliminary version of this paper appeared in Proceedings of the 2008 IEEE International Conference on Research, Innovatio
Scientific paper
We present an efficient reduction from the Bounded integer programming (BIP) to the Subspace avoiding problem (SAP) in lattice theory. The reduction has some special properties with some interesting consequences. The first is the new upper time bound for BIP, $poly(\varphi)\cdot n^{n+o(n)}$ (where $n$ and $\varphi$ are the dimension and the input size of the problem, respectively). This is the best bound up to now for BIP. The second consequence is the proof that #SAP, for some norms, is #P-hard under semi-reductions. It follows that the counting version of the Generalized closest vector problem is also #P-hard under semi-reductions. Furthermore, we also show that under some reasonable assumptions, BIP is solvable in probabilistic time $2^{O(n)}$.
No associations
LandOfFree
On Bounded Integer Programming does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with On Bounded Integer Programming, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On Bounded Integer Programming will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-11471