# Questions tagged [pseudo-polynomial]

The tag has no usage guidance.

36 questions
Filter by
Sorted by
Tagged with
61 views

### Is there an NP-hard problem that becomes polynomial when the inputs are at most $2^n$?

Let Q be a computational problem that accepts as input some $n$ non-negative integers. Is it possible (assuming $P\neq NP$) that Q is NP-hard in general, but can be solved in polynomial time when ...
• 6,132
81 views

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

As far as I know, the K coloring problem is NP-complete. However, I'm a bit confused about how to determine whether a problem is weakly or strongly NP-complete. If an NP-complete problem is decidable ...
• 21
1 vote
35 views

### Scheduling jobs with the same release time and different due dates on a single machine

Consider the problem of scheduling jobs with different lengths on a single machine while the jobs have the same release times and different due dates. The goal is to schedule the maximum number of ...
1 vote
182 views

### knapsack with graph connectivity constraints

I am looking for a variant of the knapsack problem in which the items are nodes in an undirected graph, and the knapsack must be filled with a connected subgraph. Formally: The input is an undirected ...
• 6,132
1 vote
93 views

### Is there a pseudopolynomial time algorithm for this subset sum variant?

The subset sum problem is: given a list of $n$ positive integers, and a positive number $T$, find a sub-list with largest sum that is at most $T$. The problem can be found in time polynomial in $n$ ...
• 6,132
1 vote
56 views

### The Longest Sequence of Blocks

We have n block $B_i$ $(1 \le i \le n)$, each block has 6 faces and each face material, is one of the k types (k is an input parameter). In addition, each block $B_i$ has the weight $W_i$. the ...
• 31
1 vote
75 views

### Has term pseudo-logarithmic standard meaning?

Whenever an algorithm has polynomial complexity, but exponential over the encoding of the input, it is said to be pseudo-polynomial. What about logarithmic complexity? Wouldn't be wrong to refer to ...
119 views

### Pseudo-polynomial Algorithms

Reading wikipedia I found that they give this example Consider the problem of testing whether a number n is prime, by naively checking whether no number in $\{2,3,\dotsc ,\sqrt {n}\}$ divides $n$ ...
• 263
1 vote
463 views

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

I have read Why is the dynamic programming algorithm of the knapsack problem not polynomial? and other related questions, so this is not a duplicate but just a related pair of questions to clear some ...
• 23
144 views

### Why is "encoding" important in time complexity?

I read many writing about the time complexity of 0-1 knapsack problem. (https://stackoverflow.com/questions/4538581/why-is-the-knapsack-problem-pseudo-polynomial#answer-4538668) In conclusion, the ...
• 13
1 vote
616 views

### 0-1 knapsack without repetition

My question is why O(nW) at the knapsack problem is pseudo-polynomial. I read lots of the explanation at stackoverflow, But I don't really understand it. (https://stackoverflow.com/questions/19647658/...
• 13
4k views

### Knapsack Problem with exact required item number constraint

How would we solve the knapsack problem if we now have to fix the number of items in the knapsack by a constant $L$? This is the same problem (max weight of $W$, every item have a value $v$ and weight ...
• 48
443 views

### pseudo-polynomial reduction from 3-Partition to Partition

A problem $\Pi'$ is pseudo-polynomially reducible to the problem $\Pi$ ($\Pi' \leq_{pp} \Pi$) if, for any instance $I'$ of $\Pi'$, an instance $I$ of $Π$ can be constructed in pseudo-polynomially ...
144 views

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

I have an scheduling probelm with a set of jobs $J$, with a ''non-integer'' parameter $\beta_j$, i.e. the parameter is a real number and $\beta_j \leqslant 0.5, \exists j \in J$. Since the problem ...
• 159
2k views

943 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 ...
• 397
1 vote
77 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 ...
• 439
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 ...