1
New Theories / What makes NP problems hard to solve?
« on: 16/01/2025 11:52:47 »
In my earlier thread, I discussed the problem of Riemann's hypothesis, which is an unsolved math problem to the time it was started.
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?
The Essentials of Problem SolvingQuoteAn 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?