Polynomial vs. Pseudo-Polynomial

preview_player
Показать описание
Debunking the subtle differences between the two very similar program runtimes, and highlighting why this distinction is so important.
  1. CSBreakdown
  2. Computer Science (Field Of Study)
Рекомендации по теме
Polynomial vs. Pseudo-Polynomial 0:07:13

Polynomial vs. Pseudo-Polynomial

What are pseudo-polynomial 0:06:10

What are pseudo-polynomial run times? | Knapsack Dynamic Programming

Why is the 0:06:59

Why is the knapsack problem pseudo-polynomial?

CS 5720 L16 0:13:06

CS 5720 L16 07 Knapsack Complexity and Pseudopolynomial

18. Dynamic Programming, 1:03:45

18. Dynamic Programming, Part 4: Rods, Subset Sum, Pseudopolynomial

Computer Science: Do 0:02:11

Computer Science: Do I understand pseudo polynomial time correctly? (2 Solutions!!)

Pseudo-polynomial time 0:03:06

Pseudo-polynomial time

Expressing pseudo-polynomial runtime 0:01:17

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

Pseudopolynomial Algorithm For 0:02:38

Pseudopolynomial Algorithm For Knapsack - Intro to Theoretical Computer Science

Pseudopolynomial Algorithm For 0:03:18

Pseudopolynomial Algorithm For Knapsack Solution - Intro to Theoretical Computer Science

Ford-Fulkerson pseudo-polynomial 0:01:21

Ford-Fulkerson pseudo-polynomial

Pseudo-polynomial time algorithm 0:01:56

Pseudo-polynomial time algorithm for NP-Complete Problems

Computer Science: About 0:02:26

Computer Science: About the pseudo polynomial complexity of the KnapSack 0/1 problem

Lecture 16- Tom 1:16:36

Lecture 16- Tom Fletcher: regression on manifolds: pseudo-linear, pseudo-polynomial, pseudo-kerne...

What is the 0:02:20

What is the precise definition of pseudo-polynomial time (feat. Counting Sort)

How can I 0:01:19

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

Karl Bringmann: Pseudopolynomial-time 1:01:28

Karl Bringmann: Pseudopolynomial-time Algorithms for Optimization Problems

pseudo-polynomial reduction from 0:02:07

pseudo-polynomial reduction from 3-Partition to Partition

Computer Science: Why 0:01:56

Computer Science: Why addition algorithm is not pseudo- polynomial? (2 Solutions!!)

Polynomial Time - 0:03:07

Polynomial Time - Intro to Theoretical Computer Science

Computer Science: Shouldn't 0:02:04

Computer Science: Shouldn't every algorithm run in pseudo-polynomial time? (2 Solutions!!)

Why is the 0:02:21

Why is the knapsack problem pseudo polynomial

Polynomial Time Approximation 0:01:04

Polynomial Time Approximation Scheme Solution - Intro to Theoretical Computer Science

Computer Science: Going 0:01:32

Computer Science: Going deeper with pseudo-polynomial time algorithm for set partitioning

Комментарии
Автор

Around 5:27, it is stated that it is "non-polynomially complete problem, so it's NP-complete...". Would it perhaps be better to say "non-deterministic polynomial"?

AngelExia
Автор

Just O(n^k) for some k is fine to define P problems. Because for example every problem that is O(nlogn) is also O(n^2)...

theodorosstassinopoulos
Автор

Does this mean that virtually any loop structure that iterates from say i=0 to i=n is pseudopolynomial? Because you could always have a massive "n" as input like 300 digits in your example.

letoiiatreides
Автор

Please re-do the video with clearer understanding. a 300 digit integer can be represented by about log2(300) bits. So if you increase digits, your required number of bits would grow logarithmically, not exponentially.

randomvideos
Автор

I feel like you do not understand NP vs P. Your explanation is at least wired if not flat out wrong. You simply didn't even go into the mathematical Background. Didn't argue about encoding length or any exponential function what so ever. This video does not help anyone to truly understand the issue. I'm thankful you tried to help people, but I would just delete the video if I could. Excuse my English pls.

justusrenger