Questions tagged [pseudo-polynomial]
The pseudo-polynomial tag has no summary.
36 questions
- Bountied 0
- Unanswered
- Frequent
- Score
- Trending
- Week
- Month
- Unanswered (my tags)
2
votes
0
answers
53
views
Asymptotic complexity of knapsack algorithm considering all numbers ∈ Z
In the knapsack problem, we consider numbers ∈ Z+ which gives us a run time of $O(nW)$. To my understanding, this is pseudo-polynomial and the worse case runtime is $O(n*2^{log(w)})$
My question is, ...
3
votes
2
answers
114
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 ...
2
votes
1
answer
187
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 ...
1
vote
0
answers
64
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
1
answer
245
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 ...
1
vote
0
answers
143
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$ ...
1
vote
0
answers
77
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 ...
1
vote
0
answers
100
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 ...
0
votes
0
answers
164
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$ ...
1
vote
2
answers
579
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 ...
0
votes
0
answers
187
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 ...
1
vote
1
answer
694
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/...
3
votes
2
answers
5k
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 ...
0
votes
1
answer
572
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
1
answer
187
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 ...