16 votes
Accepted

Why is the dynamic programming algorithm of the knapsack problem not polynomial?

When we say polynomial or exponential, we mean polynomial or exponential in some variable. $nW$ is polynomial in $n$ and $W$. However, we usually consider the running time of an algorithm as a ...
Tom van der Zanden's user avatar
8 votes
Accepted

Shouldn't every algorithm run in pseudo-polynomial time?

The running time is always considered with respect to the length of the input. If the input is a natural number $N\in\mathbb{N}$, then the length of the input is $n=\log N$. In that case, running ...
Ariel's user avatar
  • 13.4k
7 votes
Accepted

How is integer factoring not in $P$?

One of the things to remember when dealing with natural numbers (and others, but naturals are the central things here) is the encoding, and that the definitions of $P$ and $NP$ reference the length of ...
Luke Mathieson's user avatar
6 votes

Could this be an NP-Complete problem?

The sequence of losing positions can be found in the OEIS, A030193, as is the sequence of positions having Grundy value 1, A224839. The encyclopedia cites several relevant articles. Perhaps some of ...
Yuval Filmus's user avatar
4 votes
Accepted

Knapsack Problem with exact required item number constraint

You can transform this problem into an instance of Knapsack. Let $n$ be the number of items, $V$ be the maximum value of an item and suppose that each item weighs at most $W$ (otherwise it can be ...
Steven's user avatar
  • 29.5k
3 votes
Accepted

knapsack with graph connectivity constraints

There shouldn't be a pseudopolynomial-time algorithm; the problem is NP-hard even if all values are given in unary. We can reduce from the $\textsf{Connected Vertex Cover}$ problem in which we need to ...
Bernardo Subercaseaux's user avatar
3 votes

Why is the dynamic programming algorithm of the knapsack problem not polynomial?

I have read that one needs $\lg ⁡W$ to represent $W$ so it is exponential-time. But, I don't understand, also one needs $\lg ⁡n$ to represent $n$, no? This is a great question. You need to look at ...
David Richerby's user avatar
2 votes

Why not to take the unary representation of numbers in numeric algorithms?

In short and simple, I will show you why. Suppose, you have a factorization algorithm. Except for the small difference that one accepts integers for input and the other $Tally$. As you can see both ...
The T's user avatar
  • 319
2 votes
Accepted

Psedu-polynomial Time : Conflict with the definition of input size

First, the size of the input is the number of bits required to represent the input. When talking about complexity, we often assume that our input is represented as some bit-string. For the knapsack ...
Discrete lizard's user avatar
  • 8,248
2 votes
Accepted

How can I develop a pseudo-polynomial time algorithm for a non-integer problem?

Classifying algorithms as pseudo-polynomial time is not really a meaningful concept if there are no numbers (integers) in the instances. Of course, it is up to you to define what parts of the input ...
Pontus's user avatar
  • 687
2 votes
Accepted

Solve PARTITION-INTO-THREE-SETS in pseudo-polynomial time

Yes, there is a pseudo-polynomial algorithm for this problem. Here is a wrong algorithm. Can you spot the biggest error? Let $K=\sum_{i=1}^n{a_i}$. If $K$ is not divisible by 3, return none. Run ...
John L.'s user avatar
  • 39k
2 votes

Knapsack Problem with exact required item number constraint

Define a matrix $M$ of size $n \times W \times L$. The entry $M[i][j][k]$ denotes the maximum value of the knapsack when exactly $k$ items are chosen from $\{1,\dotsc,i\}$ and the allowed capacity of ...
Inuyasha Yagami's user avatar
2 votes
Accepted

About the pseudo polynomial complexity of the KnapSack 0/1 problem

Whether $n$ is "included in the input" or not is irrelevant. No "tricks" are being used to sneakily hide $n$ from the input by implicitly including it as the length of a list. The ...
Tom van der Zanden's user avatar
1 vote

Proof that the K coloring problem is weakly or strong NP-complete?

There are no obvious integers involved in an instance of the $K$-coloring problem (where $K$ is part of the problem and not of the input). The length of the encoding of an instance of $K$-coloring is ...
Steven's user avatar
  • 29.5k
1 vote

About the pseudo polynomial complexity of the KnapSack 0/1 problem

Suppose that there are $n$ integer weights of magnitude at most $W$. We can encode each weight in $O(\log W)$ bits, and so the total input length (in bits) is $O(n\log W)$. An algorithm is polynomial ...
Yuval Filmus's user avatar
1 vote

pseudo-polynomial reduction from 3-Partition to Partition

The claim It follows that, $\forall \Pi,\Pi' \in NP$, if $\Pi'$ is strongly NP-complete, and $\Pi' \leq_{pp} \Pi$, then $\Pi$ is strongly NP-complete. is wrong (at least for how "pseudo-...
Tom van der Zanden's user avatar
1 vote

Solving a variant of the Exact cover problem

There's no pseudopolynomial algorithm for exact cover (unless P=NP), so it is easy to show that this implies there is no pseudopolynomial algorithm for twice-exact-cover, either. For instance, here's ...
D.W.'s user avatar
  • 159k
1 vote

Shouldn't every algorithm run in pseudo-polynomial time?

If you search for the maximum of an array of n elements, the input isn't n. It's n and an array of n elements. The input size is not log n, but a least some multiple of n. And there are many, many ...
gnasher729's user avatar
1 vote
Accepted

Common subset sum fast algorithm

Yes, we shall use dynamic programming and extend our subset-sum algorithm here. Let $R(i, \ s, \ t)$ be true iff there exists a subset $K \in \{1, ... i\}$ such that $$\sum_{i \in K} a_i = s \...
Mathguy's user avatar
  • 411

Only top scored, non community-wiki answers of a minimum length are eligible