मिलान सदिशों से उत्प्रेरक वृक्ष का मूल्यांकन
arXiv:2602.14320v1 घोषणा प्रकार: नया सार: हम उत्प्रेरक-कंप्यूटिंग मॉडल (बुहरमन एट अल। STOC 2014) में वृक्ष मूल्यांकन (एस. कुक एट अल. टीओसीटी 2012) के लिए नए एल्गोरिदम देते हैं। दो मौजूदा दृष्टिकोणों का लक्ष्य कम जगह में ट्री मूल्यांकन (ट्रीइवल) को हल करना है: एक तरफ, जे. कुक और मर्ट्ज़ (एसटीओसी 2024) सुपर-लघुगणकीय स्थान $O(\log n\log\log n)$ और सुपर-बहुपद समय $n^{O(\log\log n)}$ में चलने वाले TreeEval के लिए एक एल्गोरिदम देते हैं। दूसरी ओर, बुहरमन एट अल के परिणाम के साथ संयुक्त रूप से ट्रीएवल से सर्किट मूल्यांकन तक एक साधारण कमी। (STOC 2014), लॉगरिदमिक $O(\log n)$ मुक्त स्थान और बहुपद समय में चलने वाले TreeEval के लिए एक उत्प्रेरक एल्गोरिदम देता है, लेकिन बहुपद उत्प्रेरक स्थान के साथ। हम दिखाते हैं कि बाद वाले परिणाम में सुधार किया जा सकता है। हम TreeEval के लिए लॉगरिदमिक $O(\log n)$ मुक्त स्थान, बहुपद रनटाइम और उपबहुपद $2^{\log^\epsilon n}$ उत्प्रेरक स्थान (किसी भी $\epsilon > 0$ के लिए) के साथ एक उत्प्रेरक एल्गोरिदम देते हैं। हमारा परिणाम पहली प्राकृतिक समस्या देता है जिसे लॉगरिदमिक मुक्त स्थान और यहां तक कि $n^{1-\epsilon}$ उत्प्रेरक स्थान के साथ हल करने योग्य माना जाता है, जिसे मान्यताओं के तहत भी मानक लॉगस्पेस में नहीं जाना जाता है। विलियम्स (STOC 2025) की कमी से हमारा परिणाम तुरंत उत्प्रेरक स्थान द्वारा समय के बेहतर सिमुलेशन का संकेत देता है। हमारा उत्प्रेरक ट्रीइवल एल्गोरिदम मेल खाने वाले वेक्टर परिवारों और निजी सूचना पुनर्प्राप्ति के कनेक्शन से प्रेरित है, और (समान) मिलान वाले वेक्टर परिवारों के बेहतर निर्माण से हमारे एल्गोरिदम में सुधार होगा।