Polynomial vs. Pseudo-Polynomial

[@Angel00Exia]

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"?

[@CSBreakdown]

+Samuel C. Yes, it would be more accurate to say "non-deterministically polynomially complete"

[@flo7968]

@@CSBreakdown For everybody reading this in the Future, "non-polynomially" is not inaccurate, it's wrong. NP is an upper bound and by definition contains the Problems which are verifiable in polynomial time. "Non-polynomial" implies that Problems solvable in polynomial time are not included, but obviously problems which are solvable in polynomial time, are also verifiable in polynomial time. Besides that, the video is awesome!

[@theodorosstassinopoulos6355]

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)...

[@letoiiatreides2466]

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.

[@CSBreakdown]

+John Cena Not necessarily. The operation of looping from 0 -> n, even if n is large, only requires n iterations. It would be O(n). The pseudo polynomial expression grows exponentially in the number of bits a problems representation requires. The trick is that to calculate mod inside the loop, that is extra work where the number of bits becomes relevant. It is just enough work to consider the growth of the problem exponential. Read here for more: stackoverflow.com/questions/19647658/what-is-pseudopolynomial-time-how-does-it-differ-from-polynomial-time

[@letoiiatreides2466]

+CSBreakdown That makes perfect sense! I love the videos and I hope you guys keep making more! My course content is only the textbook so these videos are a life saver.

[@randomvideos3628]

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.

[@MultiKB13]

No, your analysis is incorrect. You’re confusing the NUMBER 300 vs. a 300 DIGIT number. It takes log2(300) bits to represent the literal NUMBER 300, not a 300 DIGIT number. In his primality test example, for a given NUMBER N, you’ll have to loop N times. But if the input was the number of bits to represent N, say ‘B’, then we’ll need to loop about 2^B times to reach N, which is exponential time in respect to the size of the input. The video analysis is correct.

[@justusrenger7339]

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.

[@co88liwan31]

Thanks! really appreciate!