Podcast #128: We chat with Kent C Dodds about why he loves React and discuss what life was like in the dark days before Git. Listen now.

Questions tagged [pseudo-polynomial]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0
votes
0answers
23 views

Do pseudo-polynomial algorithms for NPC-problems scale in practice?

Given for example the NP-complete (NPC) Knapsack-problem, we know that there exists pseudo-polynomial algorithms that run in $O(n*w)$, where $W$ is pseudopolynomial. Are those algorithms useful to ...
0
votes
1answer
65 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 ...
0
votes
1answer
56 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 ...
2
votes
1answer
452 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 ...
1
vote
0answers
53 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 ...
3
votes
1answer
105 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 ...
0
votes
1answer
174 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 ...
0
votes
0answers
105 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 ...
0
votes
1answer
121 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?
1
vote
1answer
263 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 ...
2
votes
0answers
120 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} \...
2
votes
1answer
120 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}\...
10
votes
1answer
189 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: ...
3
votes
2answers
785 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 ...
2
votes
1answer
223 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_{...
12
votes
2answers
13k 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 ...
15
votes
3answers
3k 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 ...
1
vote
1answer
1k 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 ...
2
votes
1answer
3k 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 ? ...
1
vote
1answer
1k 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)...
2
votes
1answer
52 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=\...
2
votes
2answers
802 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 ...
1
vote
1answer
73 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 ...
7
votes
2answers
4k 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 ...
7
votes
2answers
1k 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;...