[alancalverd]

AFAIK eggs are graded by weight but sold by number within a weight category, so placing 6, 12 or occasionally 15 eggs in a compartmentalised box labelled "large", "medium" or  "mixed" becomes a P problem. But I heard a delightful exchange on an Irish radio phone-in some years ago:

"So the Health Department tells us it's OK to eat an egg every day."
 - "Yes, I've heard that".
"But there's only six in a box"
- "So what do you want to do about it?"
"Can we abolish Tuesdays?"

Thus neatly solving an NP problem.   

[hamdani yusuf (OP)]

Basically, complexity of a problem depends on the size of its search space, and the size of impact and cost of each step or iteration in solving it.

The cost of each step or iteration in solving a problem can also be made arbitrarily high. This can be useful for preventing brute force attacks. Instead of directly comparing the answer with the guessed value, you can make the algorithm to execute a function with arbitrary complexity using the guessed valve as the input. Only then you can verify if the guessed value matches the result using the correct answer.
So, basically the complexity of a problem can be mapped at least in three dimensional continuum of free parameter axes, which are the size of its search space, and the size of impact and cost of each step or iteration in solving it. 

[hamdani yusuf (OP)]

I can prove I?ve solved this Sudoku without revealing it

I can convince you that I?ve solved a sudoku without giving you any information about my solution. We discuss how to do this using what cryptographers call a zero-knowledge proof, and how the same tricks can be used for almost any other problem you can think of.


0:00 Intro
0:50 Interactive proofs
2:28 Graph coloring
3:22 A simple protocol
6:31 Building the full protocol
10:24 Commitment schemes
12:37 Reducing sudoku to coloring
14:28 General reduction
17:04 Discussion
19:09 Outro

[hamdani yusuf (OP)]

But what is quantum computing? (Grover's Algorithm)

Qubits, state vectors, and Grover's algorithm for search.
Instead of sponsored ad reads, these lessons are funded directly by viewers: https://3b1b.co/support
An equally valuable form of support is to share the videos.

The subtitles on this video were done using AI, and are likely imperfect, but they are open for community corrections at https://criblate.com/

Adam Brown's paper on the connection between Grover's Algorithm and block collisions:
https://arxiv.org/pdf/1912.02207

Timestamps:
0:00 - Misconceptions
6:03 - The state vector
12:00 - Qubits
15:52 - The vibe of quantum algorithms
18:38 - Grover?s Algorithm
29:30 - Support pitch
30:11 - Complex values
31:27 - Why square root?
34:01 - Connection to block collisions
35:08 - Additional resources

------------------