[Show GN: ManiSurve – 10,000개 노드 NP 문제를 0.09초 만에 해결하는 다항 시간 엔진

ManiSurve v1.5는 NP-Complete 문제를 다항 시간(P) 내에 해결하는 새로운 엔진으로, 10,000개 노드와 50,000개 간선을 가진 그래프 컬러링 문제를 0.09초 만에 해결했습니다. 이산적 충돌을 리만 다양체 위의 연속적인 곡률로 해석하여 지수 시간의 벽을 깨는 로직을 사용했습니다. 개발자는 초보 연구자로서 커뮤니티의 피드백을 요청하며, GitHub에 코드를 공개했습니다.

https://news.hada.io/topic?id=27084

#npcomplete #algorithm #graphcoloring #manisurve #computationalcomplexity

[Перевод] Генерация кроссвордов: «достаточно хорошее» решение NP-полной задачи

Генерация кроссвордов — NP-полная задача. Каждая ячейка, в которой пересекаются два слова, создаёт ограничение, которому должны удовлетворять оба слова, и эти ограничения перемножаются в сетке, приводя к комбинаторному взрыву. Эффективного алгоритма, гарантирующего решение, не существует, но вооружившись подходящими эвристиками, можно создать нечто, работающее на удивление хорошо. В конце 2021 года, уже сильно после начала локдауна, моя одержимость кроссвордом газеты The New York Times превратилась в хобби-проект. Я хотел написать приложение с кроссвордами, понял, что мне нужны сами кроссворды, попробовал сочинять их вручную, осознал унылость этого процесса и задался вопросом: можно ли генерировать их алгоритмически? В этом году я наконец-то выпустил Crosswarped для iOS и Android — игру в кроссворды, созданную на основе генератора, описываемого в этой статье.

https://habr.com/ru/articles/980182/

#кроссворды #процедурная_генерация #npcomplete #npполная_задача #словари

עקב עיכוב בטיסה הנכנסת נתקעתי לכמה שעות באתונה, וקיבלתי וואצר לבית קפה. מכיוון שיש לי כניסה ללאומג' הוואצר נוצל למתנות לילדים, ונאלצתי בלייב לפתור את בעיית ה knapsack שהיא כידוע לכל #NPComplete . בושה שאפילו היוונים משקיעים יותר בחינוך המתמטי מאשר ממשלת ישראל.

(למתעניינים ניצלתי את כל הסכום עד כדי 10 סנט, בגלל סכומים לא עגולים)

🚀 Excited to announce my 5th course, Network Algorithms and Approximations! 🎓 Explore NP-complete problems (Set Cover, Unique Coverage, etc.), approximation techniques, and applications in data science, neural nets, & network optimization.

📺 First lecture: https://youtu.be/Tnm-8xieqB4
🎥 Weekly uploads: Wednesdays at 7 PM EDT. Playlist: https://youtube.com/playlist?list=PLx7SjCaKZzEIeJxOlTuXveAE5eY7WOYB9

Plus, all 4 previous courses (Game Theory, Algorithms, Lower Bounds, Data Science) are online! 🌐 https://youtube.com/@hajiaghayi

#NetworkDesign #Optimization #NPComplete #Algorithms #DataScience #NeuralNets

In our effort to put courses online, we continue lectures on Algorithmic Lower Bound Course. Now you can watch

Lesson 4-11: Algorithmic Lower Bounds by Mohammad Hajiaghayi - NP-Completeness and Beyond

(FEEL FREE TO SUBSCRIBE TO YOUTUBE @hajiaghayi FOR FUTURE LESSONS Premiering on WEDNESDAYS)

https://youtu.be/VZyffnAb1r0 (Lesson 4: 3-Partition Problem & Proving NP-Hardness)

https://youtu.be/4fCD9_1eQw0 (Lesson 5: Puzzle Problem NP-Hardness & 3-Partition)

https://youtu.be/FIyEj72-UJQ (Lesson 6: 3-SAT Problem & Proving NP-Hardness)

https://youtu.be/tbSJzaKx2pA (Lesson 7: Puzzle Problem NP-Hardness via 3-SAT)

https://youtu.be/voRVebBsh94 (Lesson 8: Fine-grained Subcubic Complexity: Part 1)

https://youtu.be/gRURSM6QARo (Lesson 9: Fine-grained Subcubic Complexity: Part 2)

https://youtu.be/qPw82bTAXkc (Lesson 10: Fine-grained Subquadratic Complexity 1)

https://youtu.be/C6j4avVkI7U (Lesson 11: Fine-grained Subquadratic Complexity 2)

#AlorithmicComplexity,

#3SAT,

#3Partition,

#subquadratic,

#subcubic,

#Finegrained,

#HardnessExploration,

#NP,

#PSPACE,

#NPComplete,

#LogSpace,

#ExponentialComplexity,

#ParallelComputation,

#PvsNP,

#NPSPACE,

#NonDeterministicSpace, hashtag

#SavitchTheorem,

#ComplexityClasses,

#Reductions,

#ImportantProblems,

#CommunicationComplexity, hashtag

#GeometricProblems,

#AlgorithmDesign,

#ComputationalComplexity,

#TheoreticalComputerScience,

#AlgorithmicLowerBounds

For comprehensive handwritten lecture notes on this course, visit the instructor's website:

http://www.cs.umd.edu/~hajiagha/
The course textbook "Computational Intractability: A Guide to Algorithmic Lower Bounds" by Demaine, Gasarch, and Hajiaghayi is available for free at:

https://hardness.mit.edu/