সাবকোয়াড্রেটিক 3SUM এবং সাবকিউবিক APSP

আমরা 3SUM এবং অল-পেয়ার্স শর্টেস্ট পাথস (APSP)-এর পাঠ্যপুস্তক অ্যালগরিদমের উপর প্রথম বহুপদী উন্নতি দিই: আমরা দেখাই কিভাবে বহুপদী আকারের n পূর্ণসংখ্যার উপর 3SUM নির্ণয়বাদীভাবে O(n^{1.9992}) সময়ে এবং বহুপদীভাবে সীমাবদ্ধ পূর্ণসংখ্যা ওজন সহ নির্দেশিত n-শীর্ষবিশিষ্ট গ্রাফে APSP O(n^{2.9995}) সময়ে সমাধান করা যায়। এটি 3SUM এবং APSP অনুমানকে খণ্ডন করে। পরিচিত হ্রাস ব্যবহার করে, আমরা 3SUM এবং APSP অনুমানের বাস্তব-মূল্য সংস্করণ, এক্সেক্ট ট্রায়াঙ্গেল অনুমান, জিরো-ওয়েট k-ক্লিক অনুমান, এবং van den Brand, Nanongkai, এবং Saranurak-এর তিনটি আয়তক্ষেত্রাকার ইঙ্গিতযুক্ত অনলাইন ম্যাট্রিক্স-ভেক্টর অনুমানকেও খণ্ডন করি, এবং বিভিন্ন অন্যান্য সমস্যার জন্য বহুপদী গতি প্রদান করি। এই সমস্ত ফলাফল পাতলা ম্যাট্রিক্স গুণফলের জন্য একটি নতুন অ্যালগরিদম থেকে অনুসরণ করে। ধরা যাক X একটি N×D পূর্ণসংখ্যা ম্যাট্রিক্স এবং Y একটি D×N পূর্ণসংখ্যা ম্যাট্রিক্স যেখানে D ≤ N^{1/18}, এবং W সর্বাধিক N^2/√D অবস্থানের যেকোনো সেট। আমরা (XY)[I, J], (I, J)∈W, এন্ট্রিগুলি O(N^2/D^{0.063}) অপারেশনে গণনা করি, যা XY লেখার বা N^2/√D অভ্যন্তরীণ গুণফল একে একে গণনা করার জন্য প্রয়োজনীয় সময়ের চেয়ে বহুপদীভাবে কম। আমরা এই অ্যালগরিদমটি Coppersmith-এর আয়তক্ষেত্রাকার ম্যাট্রিক্স গুণন অ্যালগরিদমের একটি রূপ পরিবর্তন করে ডিজাইন করি, যা Schönhage-এর দশ-গুণ পরিচয় থেকে নির্মিত, শুধুমাত্র W-তে এন্ট্রিগুলির জন্য প্রয়োজনীয় অপারেশনগুলি সম্পাদন করতে, এবং দেখাই যে কয়েকটি অপারেশন প্রয়োজন। গ্রাফ অ্যালগরিদম হিসাবে ব্যাখ্যা করলে, এটি স্পার্স লোপসাইডেড ট্রাইপার্টাইট গ্রাফে অল-এজেস স্পার্স ট্রায়াঙ্গেল সমস্যাকে প্রকৃত সাবকোয়াড্রেটিক সময়ে সমাধান করে, যেখানে দুটি অংশে n শীর্ষবিন্দু থাকে কিন্তু একটি অংশে n^{ε} শীর্ষবিন্দু থাকে ε<0.12 এর জন্য। পরিচিত হ্রাস দ্বারা, এক্সেক্ট ট্রায়াঙ্গেল, এবং তাই 3SUM এবং APSP, এই সমস্যায় হ্রাস পায়। আমরা একটি ডেটা স্ট্রাকচার সংস্করণও দিই যা XY-এর একক এন্ট্রিগুলির জন্য প্রশ্নের উত্তর দেয়, যা আগে থেকে জানা নয়। জমা ইতিহাস: Josh Alman থেকে [ইমেল দেখুন] [v1]সোম, 5 অক্টোবর 2026 17:44:29 UTC (93 KB)

উৎস: Hacker News · সারাংশ: HeadlinesBriefing