1

New Theories / Re: What makes NP problems hard to solve?

« on: Today at 10:04:04 »

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/

2

New Theories / Re: What makes NP problems hard to solve?

« on: Today at 09:57:55 »

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

3

New Theories / Re: What makes NP problems hard to solve?

« on: Today at 09:48:32 »

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.

4

New Theories / Re: What makes NP problems hard to solve?

« on: Yesterday at 21:54:27 »

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

5

New Theories / Re: What makes NP problems hard to solve?

« on: Yesterday at 15:19:41 »

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.

6

New Theories / Re: What makes NP problems hard to solve?

« on: Yesterday at 15:17:48 »

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

7

New Theories / Re: What makes NP problems hard to solve?

« on: Yesterday at 12:38:10 »

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.

8

New Theories / Re: What makes NP problems hard to solve?

« on: Yesterday at 12:22:20 »

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?

9

New Theories / Re: What makes NP problems hard to solve?

« on: Yesterday at 12:15:51 »

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

10

New Theories / Re: What makes NP problems hard to solve?

« on: Yesterday at 11:55:58 »

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

11

New Theories / What makes NP problems hard to solve?

« on: Yesterday at 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.

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?

12

New Theories / Re: How do we measure the energy of a photon?

« on: Yesterday at 10:41:33 »

Occam's razor tells us not to make assumptions unnecessarily. Instead of saying that universe works like a computer, it's better to say that computers work like the universe, since it's already there before humans invented computer.

13

New Theories / Re: Universal Utopia? What's The Universal Terminal Goal?

« on: 15/01/2025 16:35:24 »

The Golden Age of the Middleman

The art of good business is being a good middleman?


The biggest companies that you have never heard of make billions of dollars every year by inserting themselves as wholesalers, distributors, licensors or aggregators getting between you and the factories that make your stuff.


The only problem is? everybody kinda hates middlemen? which is why ENTIRE industries have been created from the ground up to ?cut them out? by offering direct to consumer, peer to peer, direct selling, disruptive, streamlined, outlet, platformed solutions to make consuming? everything? an easier, faster and cheaper experience.


The only  problem is? it never really works, and in our venture capital fueled rush to cut out the middleman, we have just created even bigger ones.

The middleman will be replaced by machines, which will also replace the factories that make stuffs.

14

New Theories / Re: Universal Utopia? What's The Universal Terminal Goal?

« on: 15/01/2025 15:06:55 »

How to feed 10 billion people ? without destroying nature | Andy Jarvis | TED

Feeding 10 billion people without wrecking the planet means rethinking protein, from plant-based and fermented foods to lab-grown meat that tastes like the real thing. Presenting an exciting menu of sustainable options, food futurist Andy Jarvis highlights innovations, investments and policies that could help drastically lower our carbon footprint and provide everyone with the nourishment they need ? without telling anyone what to eat. (Recorded at TED Countdown Dilemma Series: Food on June 6, 2024)

This might be necessary for medium term solution. But there's a more efficient solution for food production. Which is making human body capable of synthesizing food. We can think about synthetic organelle, or symbiotic bacteria, or even non-organic things.

 

It seems that humans will be forced to form mutualistic symbiosis with ASI and robotics just like how evolutionary process had formed us in the first place.

15

New Theories / Re: Universal Utopia? What's The Universal Terminal Goal?

« on: 15/01/2025 14:59:45 »

Evolution happens at random, and competition tends towards optimisation in any particular ecological (or economic)  niche, by elimination of the less successful.

Mutations might happen randomly. Although molecular evidence show that genetic codes have different stability due to their position in the chromosomes. Error correction mechanisms also make some genes less likely to suffer permanent random mutations.
But mutation is just one part of evolutionary process. It's followed by natural selection, which is not random, unless you are willing to ignore all the information about the environmental conditions.

16

New Theories / Re: Universal Utopia? What's The Universal Terminal Goal?

« on: 15/01/2025 14:50:08 »

Wrong. There is no objective in evolution.

There is. It's to be better at survival.

17

Just Chat! / Re: Is there a universal moral standard?

« on: 15/01/2025 14:38:11 »

Spain (or Hawaii, or Norway, for that matter) is not China.

The first two videos are about China.

18

Just Chat! / Re: Is there a universal moral standard?

« on: 15/01/2025 10:18:37 »

You don't seem to follow news that coal power plants are dying.

Not in China. And from now on, not in the USA either.

Coal power stations losing billions - China?s coal-fired power boom is OVER

Coal power plant approvals in China crash as China adds 210GW of renewables

Former coal plants start new life as solar plants
Across the U.S., old coal plants are living out second lives. The sites, long a source of pollution, are now becoming resources for solar, renewable energy.

Hawaii's last coal power plant looking into green alternatives

60% of electricity in Spain comes from renewable energy

19

New Theories / Re: Universal Utopia? What's The Universal Terminal Goal?

« on: 15/01/2025 06:27:45 »

OpenAI Explains Why NOBODY Is Ready For Whats Coming?

00:00 - AI Changes Everything
00:19 - Global AI Gaps
00:48 - Sam Altman Predictions
02:15 - AI Joins Workforce
03:35 - Intelligence Cost Drops
04:47 - AI Costs Falling
05:11 - DeepSeek V3 Impact
07:00 - Desk Jobs Replaced
08:14 - Higher Business Margins
09:29 - Cognitive vs Physical
10:46 - AI Physical Labor
12:00 - Meaning Economy Rises
13:10 - Healthcare Revolutionized
14:25 - Longevity Through AI
16:00 - AlphaFold Speeds Research
20:35 - AI Overton Window
21:29 - 2030 Transformations Ahead

20

New Theories / Re: Universal Utopia? What's The Universal Terminal Goal?

« on: 14/01/2025 21:59:05 »

Goal Misgeneralization: How a Tiny Change Could End Everything

This video explores how YOU, YES YOU, are a case of misalignment with respect to evolution's implicit optimization objective. We also show an example of goal misgeneralization in a simple AI system, and explore how deceptive alignment shares similar features and may arise in future, far more powerful AI systems.

More people are being aware that we need to identify the correct terminal goal to be  internalized into the future ASI before it's too late.