# Tag Info

## Hot answers tagged pseudo-polynomial

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 ...
• 13.2k
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 ...
• 13.4k
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 ...
• 18.1k

### 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 ...
• 277k
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 ...
• 29.5k
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 ...

### 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 ...
• 81.7k

### 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 ...
• 319
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 ...
• 8,248
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 ...
• 687
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 ...
• 39k

### 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 ...
• 6,157
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 ...
• 13.2k
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 ...
• 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 ...
• 277k
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-...
• 13.2k
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 ...
• 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 ...
• 30k
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 \...
• 411

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