1.NLTS Hamiltonians จาก LTC แบบคลาสสิก (arXiv)

ผู้แต่ง :Zhiyang He, Chinmay Nirkhe

บทคัดย่อ :ในบันทึกสั้นๆ นี้ เราได้จัดเตรียมโครงสร้างครอบครัวของ NLTS Hamiltonians [FH14] ที่สมบูรณ์ในตัวเองโดยสมบูรณ์โดยอาศัยแนวคิดจาก [ABN22], [CHN+22] และ [EH17]; ข้อเท็จจริงที่ละเว้นทั้งหมดได้รับการพิสูจน์แล้วในภาคผนวก สิ่งสำคัญที่สุดคือ ไม่จำเป็นต้องใช้รหัส LDPC ควอนตัมพารามิเตอร์ที่เหมาะสมที่สุด และสามารถสร้างขึ้นจาก LTC แบบคลาสสิกอย่างง่ายเช่นโค้ดโอแนนเอ็กซ์แพนเดอร์กราฟ นอกจากนี้ยังลบข้อกำหนดอัตราคงที่ออกจากการก่อสร้าง [ABN22] เราขอแนะนำ [Nir22] สำหรับข้อมูลเบื้องต้นเกี่ยวกับปัญหา NLTS และการพิสูจน์ผลลัพธ์ของ [ABN22]

2.Transformers ใช้ตรรกะลำดับแรกด้วยตัวระบุปริมาณส่วนใหญ่ (arXiv)

ผู้แต่ง :วิลเลียม เมอร์ริล, อาชิช ซับฮาร์วาล

บทคัดย่อ :การกำหนดลักษณะโครงสร้างโดยนัยของการคำนวณภายในโครงข่ายประสาทเทียมเป็นปัญหาพื้นฐานในด้านการตีความการเรียนรู้เชิงลึก กระบวนการตัดสินใจภายในของพวกเขาสามารถบันทึกเป็นสัญลักษณ์ในตรรกะที่คุ้นเคยได้หรือไม่? เราแสดงให้เห็นว่าโครงข่ายประสาทเทียมของหม้อแปลงใดๆ สามารถแปลเป็นสูตรตรรกะอันดับหนึ่งที่มีขนาดคงที่เทียบเท่ากัน ซึ่งอาจใช้ตัวระบุปริมาณส่วนใหญ่ด้วย แนวคิดคือการจำลองหม้อแปลงที่มีวงจรเกณฑ์ที่สม่ำเสมอสูงและใช้ประโยชน์จากการเชื่อมต่อทางทฤษฎีที่เป็นที่รู้จักระหว่างวงจรและตรรกะ การค้นพบของเรายังเผยให้เห็นข้อเท็จจริงที่น่าประหลาดใจที่ว่าการคำนวณหม้อแปลงทั้งหมดสามารถลดลงเหลือเพียงการหารจำนวนเต็มสองตัว (ใหญ่) เท่านั้น แม้ว่าผลลัพธ์ของเราจะตรงประเด็นที่สุดสำหรับหม้อแปลงไฟฟ้า แต่ก็นำไปใช้ได้เท่าเทียมกันกับสถาปัตยกรรมโครงข่ายประสาทเทียมในระดับที่กว้างกว่า กล่าวคือ สถาปัตยกรรมที่มีกราฟการคำนวณสม่ำเสมอที่มีความลึกคงที่ ซึ่งประกอบด้วยส่วนประกอบโครงข่ายประสาทเทียมมาตรฐาน ซึ่งรวมถึงเครือข่ายฟีดฟอร์เวิร์ดและเครือข่ายคอนโวลูชันอล

<แข็งแกร่ง>3. เรื่องความนูนในกราฟแยก: ความซับซ้อนของแผนผัง Steiner และ Domination(arXiv)

ผู้แต่ง :อา โมหนะปรียา, พี เรนจิธ, เอ็น สาดาโกปาน

บทคัดย่อ :บทคัดย่อ เมื่อพิจารณากราฟ G ด้วยเซ็ตเทอร์มินัล R ⊆ V (G) ปัญหาทรีของสไตเนอร์ (STREE) จะขอเซต S ⊆ V (G) \ R โดยที่กราฟเหนี่ยวนำบน S ∪ R เชื่อมต่อกัน กราฟแยกคือกราฟที่สามารถแบ่งออกเป็นกลุ่มและชุดอิสระได้ เป็นที่ทราบกันว่า STREE นั้นสมบูรณ์ NP บนกราฟแยก [1] เพื่อทำให้ผลลัพธ์นี้แข็งแกร่งขึ้น เราแนะนำการเรียงลำดับแบบนูนบนพาร์ติชั่นตัวใดตัวหนึ่ง (ก๊กหรือเซตอิสระ) และพิสูจน์ว่า STREE เป็นเวลาพหุนามที่สามารถแก้ไขได้สำหรับกราฟแยกแบบทรี-นูนที่มีความนูนบนก๊ก (K) ในขณะที่ STREE เป็นแบบ NP-สมบูรณ์ บนกราฟแยกต้นไม้-นูนที่มีความนูนบนเซตอิสระ (I) เรายังเสริมความแข็งแกร่งให้กับผลลัพธ์ NP-complete ของเราด้วยการสร้าง dichotomy ซึ่งบอกว่าสำหรับกราฟแยก unary-tree-convex (กราฟแยก path-convex) STREE เป็นกราฟพหุนามที่แก้ไขเวลาได้ และ NP-complete สำหรับกราฟแยกไบนารี-ทรี-นูน (กราฟแยกหวี-นูน) นอกจากนี้เรายังแสดงให้เห็นว่า STREE เป็นเวลาพหุนามที่แก้ได้สำหรับกราฟแยกสามส่วนนูนที่มีความนูนบน I และกราฟแยกวงกลมนูนนูน นอกจากนี้ เรายังแสดงให้เห็นว่า STREE สามารถใช้เป็นเฟรมเวิร์กสำหรับปัญหาเซตที่ครอบงำ (DS) บนกราฟแยก และด้วยเหตุนี้ความซับซ้อนแบบคลาสสิก (P เทียบกับ NPC) ของ STREE และ DS จึงเหมือนกันสำหรับคลาสย่อยของกราฟแยกทั้งหมดนี้ นอกจากนี้ สิ่งสำคัญคือต้องเน้นว่าใน [2] มีการกล่าวอ้างอย่างไม่ถูกต้องว่าปัญหาในการค้นหาชุดการครอบงำขั้นต่ำบนกราฟแยกไม่สามารถประมาณได้ภายใน (1 − ε) ln |V (G)| ในเวลาพหุนามสำหรับ ε › 0 ใดๆ ยกเว้น NP ⊆ DTIME nO(log log n) เมื่ออินพุตถูกจำกัดให้แยกกราฟ เราจะแสดงว่าปัญหาเซ็ตที่มีอำนาจเหนือขั้นต่ำมีอัลกอริธึมการประมาณ 2 − 1 ซึ่งทำงานในพหุนาม |I| เวลา. สุดท้าย จากมุมมองที่กำหนดพารามิเตอร์โดยขนาดของโซลูชันเป็นพารามิเตอร์ เราแสดงให้เห็นว่าปัญหาแผนผัง Steiner บนกราฟแยกคือ W[2]-hard ในขณะที่เมื่อพารามิเตอร์เป็นความกว้างของต้นไม้และขนาดของโซลูชัน เราแสดงว่าปัญหาได้รับการแก้ไข- พารามิเตอร์ที่ลากได้ และหากพารามิเตอร์คือขนาดของโซลูชันและระดับสูงสุดของ I (d) เราจะแสดงว่าปัญหาแผนผัง Steiner บนกราฟแยกมีเคอร์เนลที่มีขนาดมากที่สุด (2d − 1)kd−1 + k เค = |ส|.