Mastodawn

🌗 計算複雜性：你所需的記憶體遠少於時間
➤ 時間與空間的劃時代差異
✤ https://blog.computationalcomplexity.org/2025/02/you-need-much-less-memory-than-time.html
最新研究表明，所有演算法都可以使用比原始演算法所需時間少得多的記憶體來模擬。Ryan Williams 的研究成果顯示，DTIME(t(n)) 包含於 DSPACE(√(t(n)log t(n)))，這相較於先前的模擬結果有顯著提升。此突破建立在James Cook和Ian Mertz的空間效率樹狀評估演算法之上，並對計算複雜性理論產生深遠影響，也可能影響 P 與 PSPACE 的分離問題。
+ 這個研究結果真是令人驚訝！一直以為時間和空間是密不可分的，現在看來事情並非如此。
+ 雖然我不是這個領域的專家，但這個發現似乎可能對未來電腦的設計和演算法的優化產生重大影響。
#計算複雜性 #演算法 #理論電腦科學

You Need Much Less Memory than Time

Just as I was complaining that we haven't seen many surprising breakthroughs in complexity recently, we get an earthquake of a result to st...

GripNews Dec 4, 2023

🌘 一個聽起來簡單的問題對我們的宇宙來說數字太大了
➤ 當一個5歲的孩童面臨比我們宇宙還大的數字
✤ https://www.quantamagazine.org/an-easy-sounding-problem-yields-numbers-too-big-for-our-universe-20231204
研究人員證明，導航某些向量系統是最複雜的計算問題之一。
+ 這個問題的複雜性真是出乎意料。
+ 數字的規模實在是難以想像。
#計算複雜性 #向量系統

An Easy-Sounding Problem Yields Numbers Too Big for Our Universe | Quanta Magazine

Researchers prove that navigating certain systems of vectors is among the most complex computational problems.

Quanta Magazine

GripNews Dec 4, 2023

🌘 【計算複雜性：非原始遞迴函數在哪裡自然地出現？】
➤ 化學反應網絡的可及性問題及其與非原始遞迴函數的關聯
✤ https://blog.computationalcomplexity.org/2023/12/where-do-non-primitive-recursive.html
這篇文章探討非原始遞迴函數在哪些自然問題中自然地出現。作者與讀者討論瞭如何避免使用WHILE迴圈以及其他相關問題，並提出了一些與非原始遞迴函數相關的隨機思考。此外，讀者也提到了化學反應網絡的可及性問題，這是一個自然問題，與非原始遞迴函數有著密切的聯繫。
+ 這篇文章提出了一些有趣的觀點，並帶來了一些新的思考。對於計算複雜性和非原始遞迴函數感興趣的人值得一讀。
+ 化學反應網絡的可及性問題顯示了非原始遞迴函數在其他領域中的應用，這是一個有趣的觀點。這篇文章引發了我對這個領域更深入的興趣。
#計算複雜性 #非原始遞迴函數 #自然問題

Where do Non-Primitive Recursive Functions come up NATURALLY?

The following is a conversation between Clyde Kruskal and Bill Gasarch. CLYDE: Bill, a student, Ian Roberts, asked me if there are any non...

GripNews Nov 7, 2023

🌗 計算複雜性：在過去的日子裡，我們使用打孔卡片。人們是如何應對的？
➤ 過去的打孔卡片時代和人們的應對方式
✤ https://blog.computationalcomplexity.org/2023/11/in-bad-old-days-we-had-punchcards-how.html
這篇文章回顧了過去使用打孔卡片的時代，並探討了人們當時是如何應對這種介面的。作者分享了自己在大學時代使用打孔卡片的經歷，並詢問了其他人對於打孔卡片的看法和回憶。文章中提到，雖然打孔卡片的使用非常繁瑣，但它也有一些優點，例如讓人們更加謹慎地思考和設計程式，以及培養了更好的紀律性。最後，作者提出了一個問題：為什麼不多一些人像他一樣選擇等待更好的介面呢？
+ 我很喜歡這篇文章，它讓我回想起過去使用打孔卡片的時代。雖然現在的技術更加先進，但我們應該感謝過去的先驅者為我們建立了這個電子社會。
+ 這篇文章讓我想起了我在大學時代使用打孔卡片的經歷。雖然當時很繁瑣，但我認為這種經歷培養了我的耐心和紀律性，對我的職業生涯有所幫助。
#計算複雜性 #打孔卡片 #電腦科學

In the bad old days we had Punchcards. How did people deal with that?

In the fall of 1976 I started as a Freshman at SUNY Stony Brook intending to major in Math and Computer Science. I took Honors Calculus I a...

GripNews Jul 30, 2023

🌗 計算機科學家發現主要研究算法的限制
➤ 梯度下降算法的限制和困難
✤ https://www.quantamagazine.org/computer-scientists-discover-limits-of-major-research-algorithm-20210817/
最廣泛使用的數學函數求最大或最小值的技術被證明是一個基本困難的計算問題。新的研究結果解釋了梯度下降算法在某些問題上無法快速解決的原因。這個結果對於應用中的性能預期提出了限制。研究者發現梯度下降算法與一個人工構造的問題相同難度，這意味著梯度下降算法本身是一個困難的計算問題。對於需要高精度解的應用，梯度下降算法可能不是一個可行的方法。
+ 這個研究結果對於計算複雜性理論和應用研究都有重要意義。
+ 梯度下降算法在實際應用中通常表現良好，但對於需要高精度解的問題可能不適用。
#計算複雜性 #梯度下降算法 #最佳化問題

Computer Scientists Discover Limits of Major Research Algorithm | Quanta Magazine

The most widely used technique for finding the largest or smallest values of a math function turns out to be a fundamentally difficult computational problem.

Quanta Magazine

GripNews Jul 24, 2023

🌘 紋理編碼的計算複雜性
➤ 紋理編碼的計算複雜性和全面搜索方法
✤ https://fgiesen.wordpress.com/2023/07/21/computational-complexity-of-texture-encoding/
大多數標準紋理壓縮格式使用一種算法向量量化的方法，將編碼塊作為輸入來確定編碼塊的可能代碼本。此外，編碼塊的內容通常可以分為三個類別：標頭/模式位、端點和索引。編碼過程中，將端點擴展為更大的調色板，並根據某種誤差度量選擇像素所需的顏色。編碼過程中的計算複雜性取決於問題的大小和算法的效率。對於某些格式，可以使用全面搜索的方法來確定最佳編碼。然而，這種方法對於更複雜的格式並不可行。
+ 這篇文章很好地解釋了紋理編碼的計算複雜性和全面搜索方法。
#紋理編碼 #計算複雜性

Computational complexity of texture encoding

Most standard texture compression formats use a type of algorithmic vector quantization (meaning that instead of storing an explicit codebook of possible blocks, the codebook entries are determined…

The ryg blog

GripNews Jun 24, 2023

🌘 E圖提取問題是NP完全問題
➤ E圖提取問題的NP完全性
✤ https://effect.systems/blog/egraph-extraction.html
本文證明瞭E圖提取問題是NP完全問題，並通過將最小集覆蓋問題降低到E圖提取問題來證明其NP困難性。
+ 這篇文章很好地解釋了E圖提取問題的NP完全性，並提供了一個有用的降低證明。
+ 這篇文章對於計算複雜性的專業知識要求很高，但是通過簡潔的解釋和示例，使得對這個問題的理解更加容易。
#計算複雜性