[hamdani yusuf (OP)]

In my earlier thread, I discussed the problem of Riemann's hypothesis, which is an unsolved math problem to the time it was started.

The Essentials of Problem Solving

An introduction to the psychology of problem solving. Featured problems: the towers of Hanoi, the Chinese ring puzzle, the Wason 4-card selection task, the candle problem, Roman matchstick problems, and toothpick shape problems.

00:00 A quick note
00:47 The problem state space and the towers of Hanoi
4:45 Problems of representation and the Chinese ring puzzle
6:42 Context and variations of the Wason 4-card selection task
9:42 Introduction to insight problems: the candle problem
11:05 Differences between insight and incremental problems
12:15 Barriers to insight: Roman matchstick problems
17:30 Insight problems: too big of a distinction?
19:08 Well-structured and ill-structured problems
21:11 Representation and argument
23:34 Becoming a better problem solver: toothpick problems
26:45 Domain-specific knowledge and strategy change
30:55 What transfers across problem-solving domains?

IMO, the biggest factor in solving the Riemann hypothesis is about barriers to insight.
The problem is well structured. There's some problems of representation, especially in the past, where computer aided visualization wasn't a thing. Although the state space is infinite, it must not be the main difficulty here, since other problems involving infinity have been solved before.

P vs NP problem is another unsolved math problem.  They are two classifications of problems.
P problems are easy to solve and verify.
NP problems are hard to solve but easy to verify.
What makes NP problems hard to solve?

IMO, the biggest factor in determining P vs NP problem is because the problem isn't well structured/defined. What's the definitive boundary between the two classes?

[hamdani yusuf (OP)]

Here are some videos trying to explain the problem.

P vs. NP - The Biggest Unsolved Problem in Computer Science

NP-COMPLETENESS - The Secret Link Between Thousands of Unsolved Math Problems

[hamdani yusuf (OP)]

What P vs NP is actually about

What if we could run algorithms backwards? We discuss how we could do this by turning algorithms into circuits and encoding those into satisfiability problems. We then explain how it all connects to P vs NP.

#somepi

0:48 Satisfiability
2:15 Breaking RSA
8:46 General reductions to SAT
12:03 P vs NP

Blog post: https://vasekrozhon.wordpress.com/2024/08/18/what-p-vs-np-is-actually-about/

And some comments in the video.

The wildest part of P vs NP to me is just how many dead ends there have been. There's an entire genre of theorems ruling out particular ways that it might be solved, because it's far easier to prove that a line of reasoning will never resolve the issue than it is to actually solve it.

Considering most people believe it's impossible, this is actually direct progress toward proof of that.  We may have no idea how to prove that NO solution exists, but every constraint on it is progress.

This is a really good explanation! P = NP never made a satisfyingly amount of sense to me, but this helped bridge that gap a bit! Thinking of it as ?can we run solvers backwards?? is a cool approach! Quite sensible!

Remember, even if P=NP, that doesnt mean that the SAT solver algorithm is fast on a practical level. Multiplication is in O(n log n), but that algorithm hast constants that don't fit into the observable universe. Cryptography is only doomed if we find a practically "fast" algorithm

This is a great point, it's not obvious a polynomial-time SAT solver would be practical. One of the ideas we did not have time to go into is that although "existence of polynomial-time algorithm" does not imply "the existence of practical algorithm", it correlates with it heavily. Like, sure, the theoretically optimal multiplication in O(n log n) has horrible constants, but doing it by FFT in slightly worse theoretical time is extremely fast in practice.

Here's a challenge: What is the best example of a problem where we know a polynomial-time algorithm for it, but we don't have anything practical?

Are you asking, like, ?When is the average case equal to the worst case??? ?Practical? isn?t well-defined

[hamdani yusuf (OP)]

Does P = NP? | Complexity Theory Explained Visually

A visual explanation of p vs. np and the difference between polynomial vs exponential growth.
Dive deep into the enigma of complexity theory with my exploration of P vs. NP. This video delves into the fundamental principles that govern the computational universe, influenced by the brilliant minds of Von Neumann and Turing.

The origins of the universal machine and the Von Neumann architecture.
The conceptual leap from simple operations to complex algorithms.
How Von Neumann's EDVAC paved the way for modern computing.
The bottlenecks of time and space that challenge computation.
John Nash's groundbreaking perspective on computational growth.
The distinction between Polynomial (P) and Exponential (EXP) time problems.
The intriguing world of "easy to solve" vs. "hard to crack" algorithms.
The captivating realm of NP-complete problems and their significance in computing.
The 'shape of growth curve' and its impact on classifying computational problems.
Nested loops and their contribution to algorithmic complexity.
The concept of one-way functions and their critical role in computer security.
The practical implications of solving NP-complete problems.
The ongoing quest to define the boundary between P and NP.
The million-dollar question that stands at the pinnacle of computer science.
Join us on this intellectual voyage as we unravel the secrets of computational requirements, the intricacy of algorithms, and the pivotal problem that has mystified some of the greatest minds in mathematics and computer science.

Whether you're a seasoned programmer, a mathematics enthusiast, or simply curious about the inner workings of computers, this video is your gateway to understanding one of the most profound questions in computer science: Is P equal to NP?

I asked this question in the comment section of the video, related to the explanation in time stamp around 5:00

If the curve grows at n^n, what would it be classified into?

[hamdani yusuf (OP)]

Donald Knuth: P=NP | AI Podcast Clips

Donald Knuth is one of the greatest and most impactful computer scientists and mathematicians ever. He is the recipient in 1974 of the Turing Award, considered the Nobel Prize of computing. He is the author of the multi-volume work, the magnum opus, The Art of Computer Programming. He made several key contributions to the rigorous analysis of the computational complexity of algorithms. He popularized asymptotic notation, that we all affectionately know as the big-O notation. He also created the TeX typesetting which most computer scientists, physicists, mathematicians, and scientists and engineers use to write technical papers and make them look beautiful.

One of top comments

He is referring to the Robertson & Seymour graph minor theorem. Every class of graphs that is closed under minors has a finite obstruction set of "forbidden minors". This follows from the fact that the graph minor relation on the class of all graphs is a quasi-well ordering.
You can look it up on wikipedia.
The point is that this theorem constitutes a non-constructive proof for the existence of PTIME algorithms for every class of minor closed graphs. I.e. we know that a PTIME algorithm EXIST for each these classes, but we do not know what exactly the PTIME algorithm IS for each individual class, because for this you would first need to know the finite obstruction set of forbidden minors.
So this theorem contradicts the intuition that the only way to find out whether a problem is in P is to write down an explicit algorithm for solving it. You can know that a problm is in P without knowing what the PTIME algorithm for solving it is. And this might suggest that you really can't conclude that P!=NP just from the fact that no one has found a PTIME algorrithm for a NP-hard problem yet.

[Bored chemist]

IMO, the biggest factor in determining P vs NP problem is because the problem isn't well structured/defined.

And is your opinion well informed?

[hamdani yusuf (OP)]

What is "efficient" computation? (P vs NP)
Here we ask the question about what "efficient" computation should be, as well as give definitions of P (deterministic polynomial time) and NP (nondeterministic polynomial time).

[hamdani yusuf (OP)]

IMO, the biggest factor in determining P vs NP problem is because the problem isn't well structured/defined.

And is your opinion well informed?

It depends on how you define well informed.

[hamdani yusuf (OP)]

What will the P=NP proof look like? | Cal Newport and Lex Fridman

[hamdani yusuf (OP)]

Does P=NP? | Richard Karp and Lex Fridman

Richard Karp is a professor at Berkeley and one of the most important figures in the history of theoretical computer science. In 1985, he received the Turing Award for his research in the theory of algorithms, including the development of the Edmonds?Karp algorithm for solving the maximum flow problem on networks, Hopcroft?Karp algorithm for finding maximum cardinality matchings in bipartite graphs, and his landmark paper in complexity theory called "Reducibility Among Combinatorial Problems", in which he proved 21 problems to be NP-complete. This paper was probably the most important catalyst in the explosion of interest in the study of NP-completeness and the P vs NP problem.

[hamdani yusuf (OP)]

The Formal Definition of P (P vs NP)
Let?s take a deeper look at the complexity class P, and decision problems.

[hamdani yusuf (OP)]

A working definition of NP-hard (Stephen Boyd, Stanford)
Prof. Stephen Boyd, of the Dept. of Electrical Engineering at Stanford, briefly explains what NP-hard means.

This clip was taken from the Prof. Boyd's class "EE364a Convex Optimization 1" and can be found at:
http://www.stanford.edu/class/ee364a/

[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.
Let's start with a simple problem, like binary search for guessing the number game. The verification process is very simple. Just compare the answer to the hidden number.

In this case the search space is n=1000, which is equal to the explicit problem statement. The impact of each step can remove false answers by half.
If the search space is increased to 1 million, it would take longer to solve. In general, if the search space is n, the number of steps needed to solve it is around log(n).

[hamdani yusuf (OP)]

Here's a modified version of the search problem above, from the search space side. Guess a number between 0 and 2^n. Again, the verification process is easy. But the solution would take log(2^n) = n steps.
It would be even longer to guess a number between 0 and n^n.

[hamdani yusuf (OP)]

Here's a modified version of the search problem above, but now from the iterative process side. Guess a number between 0 and n. But you are not allowed to ask if it's higher or lower than a specified number. You are only allowed to ask if they are equal.
In the worst case, it would take n guesses to get the right answer.

Alternatively, you are told if the difference is less than 10. Or 100.

[hamdani yusuf (OP)]

Here's a modified version of the search problem above, from the search space side. Guess a number between 0 and 2^n. Again, the verification process is easy. But the solution would take log(2^n) = n steps.
It would be even longer to guess a number between 0 and n^n.

The size of the problem can be made to look deceptively small. For example, binary search for a natural number up to googol needs up to 333 steps, because a googol requires 333 bits to express in binary. When the upper limit is increased to a googolplex, the number of steps to solve it increases to around 3.32x10^100.

The size of search space can be increased arbitrarily without obviously increase the specific number in the problem statement, e. g by increasing the dimension of the search space, or using combinatorics which effectively enlarge the search space exponentially.

[hamdani yusuf (OP)]

Here's a modified version of the search problem above, from the search space side. Guess a number between 0 and 2^n. Again, the verification process is easy. But the solution would take log(2^n) = n steps.
It would be even longer to guess a number between 0 and n^n.

The size of the problem can be made to look deceptively small. For example, binary search for a natural number up to googol needs up to 333 steps, because a googol requires 333 bits to express in binary. When the upper limit is increased to a googolplex, the number of steps to solve it increases to around 3.32x10^100.

The size of search space can be increased arbitrarily without obviously increase the specific number in the problem statement, e. g by increasing the dimension of the search space, or using combinatorics which effectively enlarge the search space exponentially.

If the upper limit of the number to guess is increased to Graham's number, the expected time to solve the standard binary search would be impractical, even if it's still called an "efficiently solvable" problem.
Even though Graham's number is a very large number, it's still far from infinity. Graham-plex would be much larger, but still far from infinity.

[hamdani yusuf (OP)]

The Miracle Solution to This 100 Year Old Geometry Problem

In this video, we cover an exciting new result in mathematics - the Empty Hexagon Problem has finally been solved, bringing a ?happy ending? to a 100-year-old mathematical journey! It started with a simple idea from the 1930s, and evolved into a rich history of geometric questions, culminating in a spectacular and lucky solution in 2024 that makes use of the newest developments in SAT solvers, a computerized proof method, filling in the last piece of the puzzle.

Special thanks to Professor Marijn Heule and Carnegie Mellon University for sponsoring this video, to Joe Horton, Bernardo Subercaseaux, and Cayden Codel for their help with the project.

[alancalverd]

...and yet...fruits and vegetables come in all sorts of masses, but every bag of potatoes or apples in the supermarket contains exactly 1 kg of produce. Obviously it hasn't taken a billion years to sort a ton of spuds into a thousand bags - more like an hour. What do farmers know, that mathematicians don't?

[hamdani yusuf (OP)]

...and yet...fruits and vegetables come in all sorts of masses, but every bag of potatoes or apples in the supermarket contains exactly 1 kg of produce. Obviously it hasn't taken a billion years to sort a ton of spuds into a thousand bags - more like an hour. What do farmers know, that mathematicians don't?

Don't forget about eggs, which is trending now. At least in US.
The value is not exact. It's approximation within some convenient limits.