1

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

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

2

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

« on: Today 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?

3

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

« on: Today 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

4

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

« on: Today 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

5

New Theories / What makes NP problems hard to solve?

« on: Today 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?

6

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

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

7

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

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

8

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

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

9

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

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

10

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

« on: Yesterday at 14:50:08 »

Wrong. There is no objective in evolution.

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

11

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

« on: Yesterday at 14:38:11 »

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

The first two videos are about China.

12

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

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

13

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

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

14

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.

15

New Theories / Re: Origin of magnetic force

« on: 14/01/2025 13:59:34 »

A comprehensive theory of magnetic force should be able to explain various phenomena, including this one.

Physics Demo -- Jumping Ring

A solid metal ring is placed on an iron core whose base is wrapped in wire. When DC current is passed through the wire, a magnetic field is formed in the iron core. This sudden magnetic field induces a current in the metal ring, which in turn creates another magnetic field that opposes the original field. This causes the ring to briefly jump upwards.

If there is a cut in the ring, it cannot form current inside it, and thus will not jump.

When the ring is cooled in liquid nitrogen, the resistance of the metal is lowered, allowing more current to flow. This lets the ring jump higher. However, the magnetic field curves away at the top of the iron coil, meaning with DC power, the ring will never fly off the top.

When AC current is passed through the wire, the ring flies off the top of the iron core.  This is due to the fact that the current lags the emf by 90 degrees in inductors (which is what we have here).  This yields forces on the ring that are always pointing upwards, even as the current oscillates.

Some discussion in the comments section.

No, the current inducted in the ring is always the opposite direction of the current in the coil, so the magnetic field of the ring always opposes the iron core's, and always is repelled. Think of the AC current demo, the current's direction is switching 60 times a second, but the ring only moves away from the coil.

well its not exactly accurate although close. When dc is connected you have an initial changing magnetic field- as the dc current rapidly changes from zero to full current flow, this change in magnetic field induces current in the ring and it jumps. But the dc current reaches a peak and is then steady non changing current, therefor can no longer induce current in the ring. In the ac current, the magnetic field is constantly changing, therefor current constantly induced in the ring, so keeps goin

What's the relativistic version of this experiment?

16

Science Experiments / Re: What phenomena can be demonstrated by a cheap high voltage generator?

« on: 14/01/2025 12:34:51 »

But the experiment in another video shows somewhat different result.

Here is an electrogravity experiment conducted on a torsion pendulum, electrostatically shielded inside a Faraday cage. The gravitational like force seems to penetrate the metal cage and exert a force upon the aluminum torsion pendulum within.. The field is a high voltage DC electrostatic field generated by a little high voltage multiplier. The results are reminiscent of the research done by Townsend Brown, on flying disc propulsion systems.

I'm curious what makes the difference. Any suggestion?

17

New Theories / Re: How close are we from building a virtual universe?

« on: 14/01/2025 12:27:22 »

How Your Brain Chooses What to Remember

In this video, we explore how the brain tags which memories to keep and the role of a special brain wave ? a hippocampal sharp-wave ripple in this process.

Outline:
00:00 Introduction
01:11 Sharp-Wave Ripples
04:38 Memory Consolidation
6:36 Experimental Setup
07:58 UMAP & Population Activity
10:33 Maze Manifold
12:02 Decoding Ripple Content
13:57 Putting it together
15:42 Brilliant.org
16:56 Outro

18

Science Experiments / Re: What phenomena can be demonstrated by a cheap high voltage generator?

« on: 14/01/2025 11:43:03 »

Here's a video demonstrating Faraday cage with electrostatics.
https://youtube.com/shorts/2hBkg6kQ_Ss?feature=shared


Professor Krishna Rajagopal explains Faraday Cages and why it's not such a bad thing if you're in a lightning storm as long as you're inside a car.

19

Just Chat! / Re: What's your advice on writing a series of story?

« on: 14/01/2025 11:03:48 »

EVERY Way AI Can Help Authors in 2025

Timestamps
Introduction 00:00
Pre-Writing 00:40
Writing & Editing 05:51
Marketing For Authors 15:56
Learning 22:43
Other Suggestions For Authors 25:57
Write A Book Using AI 30:00
-
#AuthorTools #AIWriting #AuthorsTips

20

New Theories / Re: How close are we from building a virtual universe?

« on: 14/01/2025 09:09:32 »

Same old question: if an autonomous vehicle kills someone, who is liable?

It depends on several factors.
Autonomous level of the vehicle itself,
Terms and conditions of operating the auto mode, which often different among manufacturers.
Chronology of the incident.
Is there intentional activity leading to the incident.
Is it a suicide. Or homicide.
Etc.