[a / b / c / d / e / f / g / gif / h / hr / k / m / o / p / s / t / u / v / vg / vm / vmg / vr / vrpg / vst / w / wg] [i / ic] [r9k / s4s / vip] [cm / hm / lgbt / y] [3 / aco / adv / an / bant / biz / cgl / ck / co / diy / fa / fit / gd / hc / his / int / jp / lit / mlp / mu / n / news / out / po / pol / pw / qst / sci / soc / sp / tg / toy / trv / tv / vp / vt / wsg / wsr / x / xs] [Settings] [Search] [Mobile] [Home]
Board
▼ Settings Mobile Home
4chan
/g/ - Technology


Thread archived.
You cannot reply anymore.




File: 1654699532980.png (937 KB, 1080x1048)
937 KB PNG
Explain what is the exponential time hypothesis and why it matters to CS fags?
>>
new thing to point at to pretend AI slop has any real value
>>
I don't know, man. Exponential numbers are like numbers with a small little teeny-tiny itsy-bitsy minuscule not that big number above, but you shouldn't judge too early, because when you add those small little teeny-tiny itsy-bitsy minuscule not that big numbers to normal numbers, the sum can get pretty big. That's really crazy, dude. But what's even crazier is when time is exponential, because it grows really quick. Life moves on like that, one day you ask yourself where all this time went and it's all the fault of the small little teeny-tiny itsy-bitsy minuscule not that big number.

...something like that.
>>
>>110185725
It means all your bitcoin will be worthless soon
>>
>>110185725
The Exponential Time Hypothesis (ETH) is an unproven conjecture in theoretical computer science that says certain computational problems fundamentally require exponentially increasing amounts of time as their size grows.

In simple terms: Some problems become so difficult as they get bigger that no clever algorithm can make them efficiently solvable in every case.

### Example: The 3-SAT problem

Imagine you're trying to solve a logical puzzle involving hundreds of true/false variables.

As the number of variables increases, the possible combinations double with each additional variable.

| Variables | Possible combinations |
| --------- | --------------------- |
| 10 | 1,024 |
| 20 | 1,048,576 |
| 30 | 1.07 billion |
| 50 | 1.13 quadrillion |
| 100 | 1.27 nonillion |

These are the combinations a brute-force algorithm might need to consider, not necessarily the number an optimal algorithm must examine.

### What ETH actually claims

ETH states that 3-SAT cannot be solved in subexponential time in the worst case.

Mathematically, it rules out algorithms running in:

2^{o(n)}

where is the number of variables.

### Why is this important?

* It helps establish fundamental limits on what computers can efficiently calculate.

* It is stronger than the famous P ≠ NP conjecture.

* It suggests that even vastly more powerful conventional computers cannot eliminate exponential scaling for certain problems.

The fascinating part: Nobody has proven ETH. It's entirely possible that someone could discover an algorithm that disproves it, fundamentally changing our understanding of computational complexity.

And importantly, ETH concerns computation time, not physical time or Einstein's theory of relativity.
BTC
bc1qtm4rep7kyp2p28hlkfktpnd0j7uew47vnt2mev
LTC
ltc1q9xlaysse0mpfwf025esd69kt9zu3md22gh23du
ETH
0x6abA18D203520c8F90ca63eE7426a7bC345D98e6
SOL
E5ekoiauCR8yiNp451dmuPzhUxo84P5x3m9WJBK5kxZe
XRP
r3jYXNdMk2Vz5hXhKCKE9re8uz93JQFG1r
DOGE
DSBq5jRWkiwmEh1G7zBwmQDgRkvRr61fmb
XMR
85CTwq5wGjWZw5GgzgwZPrHyZxpLXMK5oZSSSk5j4x9w1bpqzisaWAUZYaAPfh6rP2MZJcaFqF1XmEzkw6YCqJSS2Txu6Z8




Delete Post: [File Only] Style:
[Disable Mobile View / Use Desktop Site]

[Enable Mobile View / Use Mobile Site]

All trademarks and copyrights on this page are owned by their respective parties. Images uploaded are the responsibility of the Poster. Comments are owned by the Poster.