Questions tagged [pseudo-polynomial]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
1 vote
0 answers
44 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$ ...
user avatar
1 vote
0 answers
48 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 ...
user avatar
  • 21
1 vote
0 answers
46 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 ...
user avatar
0 votes
0 answers
53 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$ ...
user avatar
  • 263
1 vote
2 answers
213 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 ...
user avatar
  • 23
0 votes
0 answers
85 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 ...
user avatar
1 vote
1 answer
405 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/...
user avatar
3 votes
2 answers
2k 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 ...
user avatar
0 votes
1 answer
302 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 ...
user avatar
0 votes
1 answer
119 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 ...
user avatar
  • 159
2 votes
1 answer
2k views

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

Let PARTITION-INTO-THREE-SETS be defined as following: Input: Positive integers $a_1, ..., a_n$ Problem: Are there three pairwise disjoint sets $I, J, K \subseteq \{1, ..., n\}$ with $I \cup J \cup ...
user avatar
1 vote
0 answers
108 views

Exact cover with cover size known

I know that the exact cover problem has a pseudopolynomial algorithm when the cover size is a given constant (as here: Is set cover still NP-complete if you have a given k?). However, I am interested ...
user avatar
3 votes
1 answer
222 views

Solving a variant of the Exact cover problem

I am trying to solve a variant of the Exact cover problem where every element has to be covered exactly twice instead of once ( i.e. has to be in exactly two sets that are part of the cover). Now, it ...
user avatar
0 votes
1 answer
565 views

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

From wikipedia In computational complexity theory, a numeric algorithm runs in pseudo-polynomial time if its running time is a polynomial in the length of the input (the number of bits required ...
user avatar
0 votes
0 answers
127 views

there exists a O(n) algorithm for subset sum under certain conditions?

I was wondering if anybody knows if there is an algorithm for Subset-sum, preferably exact, having a $O(n)$ Time Complexity or near-linear ($n$ = number of elements in the input set) I remember that ...
user avatar
0 votes
1 answer
186 views

Whether the algorithm is polynomial or not with input size which is not polynomial [closed]

A problem may require memory space which is not polynomial with respect to the input size but may still have polynomial run time. Is this true or false? and why? any idea?
user avatar
  • 17
1 vote
1 answer
432 views

Solving Subset Sum Without the Use of Dynamic Programming

I am looking for algorithmic techniques to solve the Subset Sum Problem in pseudopolynomial time. There is, of course, a textbook dynamic programming approach for Subset Sum. Have any other ...
user avatar
  • 13
3 votes
0 answers
182 views

Is there a pseudo polynomial time algorithm for this 0-1 quadratic subset sum problem?

Say that we have some (integer) weights $w_{1,1},w_{1,2},...,,w_{m,m}$ and a target sum $W$. Suppose that we want to find whether there are $a_1,...,a_m \in \{0,1\}$ such that $$\sum_{i = 1}^{m} \...
user avatar
  • 168
2 votes
1 answer
169 views

How is integer factoring not in $P$?

Everyone keeps claiming that integer factoring is in $NP$ but I just don't get it... Even with the simplest algorithm (division with all integers up to $\sqrt{n}$) the complexity should be $\sqrt{n}\...
user avatar
10 votes
1 answer
256 views

Could this be an NP-Complete problem?

Consider the following problem statement: Given an initial number, you and your friend take turns to subtract a perfect square from it. The first one to get to zero wins. For example: ...
user avatar
6 votes
2 answers
1k views

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

Wiki says a numeric algorithm runs in pseudo-polynomial time if its running time is polynomial in the numeric value of the input, but is exponential in the length of the input – the number of bits ...
user avatar
  • 205
2 votes
1 answer
307 views

Common subset sum fast algorithm

Suppose of I two sets of $n$ integers bounded in $[-B,B]$. The integers are $$a_1,\dots,a_n$$ $$b_1,\dots,b_n$$ I want to find if there is a common subset $I\subseteq\{1,\dots,n\}$ such that $$\sum_{...
user avatar
14 votes
2 answers
29k views

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

The dynamic programming algorithm for the knapsack problem has a time complexity of $O(nW)$ where $n$ is the number of items and $W$ is the capacity of the knapsack. Why is this not a polynomial-time ...
user avatar
  • 457
16 votes
3 answers
5k views

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

A pseudo-polynomial time algorithm is an algorithm that has polynomial running time on input value (magnitude) but exponential running time on input size(number of bits). For example testing whether ...
user avatar
  • 1,417
1 vote
1 answer
2k views

Complexity of dynamic programming algorithm for Knapsack

Dynamic programming algorithm for Knapsack is stated to have complexity $\mathcal O (nW)$. However, I've also seen the complexity stated as $\mathcal O (n^2V)$, where $V=\max v_i$. (Here $n$ is the ...
user avatar
  • 491
2 votes
1 answer
5k views

Whats is the meaning of polynomial run-time in input size ? [duplicate]

If an algorithm runs in exponential time with exponential input then we say it runs in polynomial time ? Why ? Doesn't the algorithm run in exponential time anyway ? How the input size affects ? ...
user avatar
1 vote
1 answer
2k views

Partition partition with constraint of equal size

I see the problem here which is the well know partition problem but with constraint that the size of both sets must be equal. I look at the answer and I don't understand that why Colin said add max(S)...
user avatar
2 votes
1 answer
63 views

Expressing pseudo-polynomial runtime solely in terms of the input size

In case we have an algorithm which is pseudo-polynomial and runs in $O(n^2C)$ for some $C$ that is encoded in binary. Is it correct to say that if $C=2^n$ then $O(n^2C)=O(n^22^n)$ and because $n=\...
user avatar
3 votes
2 answers
892 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 ...
user avatar
  • 377
1 vote
1 answer
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 ...
user avatar
8 votes
2 answers
6k 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 ...
user avatar
7 votes
2 answers
2k 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 value;...
user avatar
  • 3,610