The tag has no wiki summary.

learn more… | top users | synonyms

2
votes
2answers
586 views

Why addition algorithm is not pseudo- polynomial?

There is something I don't understand. In the Subset Sum problem, in the Dynamic Programming solution, because of binary representation of the sum T, we say it is pseudo-polynomial in run time; we ...
0
votes
0answers
42 views

Is addition polynomial if you add exponential numbers? [closed]

The addition algorithm is polynomial (as far as I know, perhaps I'm wrong). Suppose that $n$ is the number of numbers to be added, and tghe largest one of them is $2^n$. Is this problem still ...
0
votes
1answer
65 views

An algorithm for making 2 carts meet [closed]

Say I have 2 carts on an infinite railroad, each cart is initially under a lamp. There are only 2 lamps, and they are at a fixed location, hence they don't change their location. The distance between ...
4
votes
1answer
740 views

Do I understand pseudo polynomial time correctly?

The running time of knapsack is $O(n*W)$, but we always specify that this is only pseudo-polynomial. I was wondering if somebody could tell me if I understand the notion of pseudo-polynomial time ...
5
votes
2answers
268 views

Weak and strong completeness

What does a pseudo-polynomial algorithm tell us about the problem it solves? I don't see how running time improves if the algorithm is exponential in the input length and polynomial in the input ...