سياسة من الجزء السفلي من الجانب المقعر من غير معبد،
تقارير و qubit | عدد ملفه QbitAI
هناك الكثير من التخمين في الرياضيات في العالم، مثل التخمين غولدباخ، فرضية ريمان، بعض المشاكل التي تعاني منها البشرية ينتشر فيه مرض لعدة قرون.
لو يوم واحد، شخص قفز فجأة وقال: "ليس لدي سوى بضع صفحات، كما يتضح من XX تخمين" الجميع سوف أعتقد أن هذا الرجل هو "تقسيم الشعب".
في الآونة الأخيرة، كان هناك عالم الرياضيات الصينية هوانغ هاو أعلن أنه ثبت التخمين نظرية الكمبيوتر المتعثرة لمدة 30 عاما، ولكن فقط ورقتين من الورق . للوهلة الأولى إلى الأخبار، قد يكون رد فعل كثير من الناس الأول: ليست "المواضيع العامة"، أليس كذلك؟
ومع ذلك، فإن الأمور ليست بهذه البساطة. هوانغ هاو قراءة التاريخ سنجد أن تخرج من دائرة الرياضيات في جامعة بكين، وحصل في عام 2012 على شهادة الدكتوراه في جامعة كاليفورنيا، الآن هو أمريكا جامعة إيموري أستاذ مساعد قسم الرياضيات وعلم الحاسوب.
هوانغ هاو يتم حل المشكلة فعلا. وقدم اثنين من البراهين، ما يكفي لفهم درجة من المعرفة. الرياضيات الزملاء بعد أن قرأت، كل ما الطريق إلى الحكمة ريال أعجب.
سنحاول استعادة الطريق و qubit شعبية الإثبات، وعلى حل هذا اللغز معا القرن - وظيفة منطقية حساسية تخمين (وظيفة منطقية التخمين حساسية).
أولا، دعونا نبدأ الحديث عن وظائف منطقية.
وظيفة منطقية
(وفيما يلي شرح لمهام منطقية، والطلاب هم على دراية البرمجة يمكن القفز مباشرة إلى الجزء الثاني).
ونحن نعلم، من قبل مجموعة من الدوائر الرقمية بوابة المنطق في تحقيق أي من وظائف، وهما معظم بوابة المنطق المشترك هو بوابة AND و OR .
والبوابة (AND) فقط عندما تكون جميع مدخلات 1، سوف يكون الإخراج 1، النواتج خلاف ذلك 0.
أو (OR) طالما مدخل واحد هو 1، والناتج هو 1 فقط إذا كان الإدخال عن الصفر، والناتج هو 0.
أيضا في المدخل هو (1،1) من هذه القضية، وسوف يكون الباب جدا حساس ما دام واحد من التغييرات المدخلات، والنتيجة يصبح صفرا. البوابة أو فقط عند حدوث تغييرات جميع المدخلات اثنين، سيتم تغيير نتيجة إلى 0.
واثنين فقط من المدخلات قليلا وOR بوابات، هو أبسط الحالات. عندما تكون هناك ن المدخلات قليلا المدخلات، ويصبح الوضع معقدا.
وكمثال على ذلك كل يوم، عند توفير المال لسنوات، وأخيرا جمع الدفعة الأولى، انتقل إلى البنك لتقديم طلب للحصول على قروض المنزل.
صراف البنك يمنحك الجدول، وهناك العديد والعديد من الأسئلة، كنت يمكنك الإجابة بنعم او لا فقط . في نهاية المطاف كنت في ملء محتوى تتم معالجة عملية معقدة، ولكن لا يمكن الحصول على قروض لالاستنتاجات الخاصة.
هذه العملية هي المدخلات متغير منطقية (نعم أو لا)، والناتج هو متغير منطقية (سواء للموافقة على القرض)، وبالتالي هي وظيفة منطقية .
بعد ذلك قمت مرة أخرى في وقت لاحق، التي يمكن الإجابة على بعض الأسئلة، في المقابل، قد تكون أيضا قادرة على تطبيق من خلال. في نهاية المطاف وجدت أنك بحاجة إلى التخلص من أكثر من 7 قضايا، من أجل تغيير النتيجة الموافقة.
لذلك نقول، وظيفة منطقية في ظل ظروف الإجابة الأولية حساسية هو 7 .
لوظيفة منطقية F، في حالة وجود بعض مدخلات العاشر (x هو متغير منطقية ن بت)، عندما يكون هناك أكثر من تغيير متغير منطقية، ستكون النتيجة عكس الصورة. ونحن نقول ان المنطقية وظيفة و هي حساسية الإدخال عندما x غير الصورة (و، خ).
كل حساسية الصورة (و، خ) ويسمى الحد الأقصى لحساسية الصورة المنطقية وظيفة و.
في عام 1989، نيسان وSzegedy اثنين تخمين، S هو متعدد الحدود في ن و. هذا هو وظيفة منطقية حساسية تخمين (وظيفة منطقية التخمين حساسية).
منذ حساسية منطقية يظهر ظائف الظن، فقد كان واحدا من الأسئلة المفتوحة في معظم محيرة النظري علم الكمبيوتر. أنه لا يحل يحل دائرة المنطق العديد من المشاكل خوارزمية النظرية، مثل لدينا التكافؤ المعروف ن بت إشارة الثنائية.
أصبحت لعبة هندسية
لكننا نريد دليلا مباشرا حساسية وظيفة منطقية تخمين من الصعب جدا. لحسن الحظ، في عام 1992 اثنين من علماء الرياضيات Gotsman وLinial تحولت بذكاء قبل أن تتحول إلى لعبة هندسية الشعبية.
يتم تحويل الدوائر الرقمية أنهم ن بت إلى قمة المكعب في الفضاء ن الأبعاد.
على سبيل المثال، 2 بت إدخال ما مجموعه أربعة احتمالات: 00،01،10،11. الموافق أربعة القمم من مربع: (0،0)، (0،1)، (1،0)، (1،1). المكعب هو مساحة مربع ثنائي الأبعاد.
وبالمثل، إذا 3 بت، ثمانية القمم تتوافق مع مكعب ثلاثي الأبعاد، وذلك لأبعاد أعلى.
في المكعب، واثنين من القمم المجاورة هناك فرق واحد فقط بين القيم تنسيق ، 0 و 1 على التوالي، متطابقة مع القيم تنسيق أخرى.
وبالتالي، من قمة الرأس المكعب انتقل الى القمم المجاورة لها، وهو ما يعادل وظيفة منطقية من البتات المدخلات مقلوب. (آه رائع!)
منذ المدخلات وظيفة منطقية يمكن استخدامها لتمثيل إحداثيات الرأس، خرج بعد ذلك؟ نحن يمكن تعريفها في لونين.
على سبيل المثال، مع 0 الأحمر، الأزرق يمثل 1 . إذا كان أحمر على الرأس فهذا يعني أن قمة تنسيق قيم ثلاثة أجزاء تتكون من 3 المدخلات وظيفة منطقية سوف يكون صفرا.
على سبيل المثال:
في وظيفة منطقية على هذا الرقم، إذا كان الإدخال (0،1،1)، فإن الناتج يكون واحدا.
إذا وضعنا الوجه الأول، وظيفة منطقية لحسن الحظ ليست حساسة لهذا التغيير، والناتج هو لا يزال 1، وهذا الرقم يعادل قمة انتقل إلى اليمين منه، أو اللون الأزرق.
ومع ذلك، بعد الدالة المنطقية الوجه الثالثة هي حساسة لهذا التغيير، يصبح الناتج صفر، المقابلة لقمة انتقل أدناه لونه من الأزرق إلى الأحمر.
إذا كان في بعض الحالات، أدخل نتيجة أي حدث واحد من الانقلاب، سوف يكون الإخراج من 1 إلى 0، وهذا يعني حول النقطة الزرقاء والحمراء، وحساسية هذه النقطة هي 0، لا نقطة زرقاء الموصولة به مباشرة.
وهو نفس عدد النقاط اللون حول نقطة، هذا وظيفة منطقية تساوي حساسية قمة. حساسية وظائف منطقية هي أن جميع القمم في حساسية الحد الأقصى.
وهكذا وظيفة منطقية يمكن خفضها الى مشاكل حساسية بسيطة تخمين في مكعب N-الأبعاد:
إذا المكعب ن الأبعاد أكثر من نصف رأس مصبوغ أحمر، والباقي مصبوغ الزرقاء، النقطة الحمراء ما إذا كانت هناك دائما بعض الجيران ونفس اللون؟ إذا كان الأمر كذلك، وعدد من النقاط الحمراء حول أكثر من غيره هو كم؟
Gotsman وLinial اثنين من الكلمات الأصلية هو هذا:
دعونا S يكون المكعب الزائدي ن الأبعاد المنطقية {0،1} ن فرعية تعسفية حجم 2N-1 + 1. لذلك يجب أن تكون هناك نقطة في S، جار واحد على الأقل في S نورث كارولاينا. (2N-1 + 1 هو بالضبط من العدد الإجمالي من القمم مكعب ن الأبعاد أكثر من نصف).
حيث c هي ثابت تتراوح بين 0 و 1، يمكننا أن نرى ج الخلفية = 1/2.
إذا مصبوغ قمة الرأس الحمراء يساوي بالضبط إلى نصف العدد الإجمالي من القمم. ويمكن أن تكون مجاورة لبعضها البعض. على سبيل المثال يمكن العثور عليها في المكعب ثلاثي الأبعاد: أربع نقاط (0،0،0)، (1،1،0)، (1،0،1) و (0،1،1) هي بالضبط قطري قطري الخط. (النقطة الحمراء في الشكل أدناه)
ومع ذلك، ما دام حتى نقطة واحدة أكثر من الزيادة في الطلاء الأحمر، فإنه يجب أن تظهر بين نقطة الاتصال الحمراء.
انفجار إلهام
حتى لو وظيفة منطقية حساسية تخمين وقد تم بالفعل مبسطة في قبل 27 عاما، ولكن المشكلة لا تزال مستمرة لتكون قيد الانتظار لمدة 20 عاما.
حتى قبل سبع سنوات، عندما الدكتور هوانغ هاو قد تخرج لتوه، وأستاذ الرياضيات في جامعة ولاية نيو جيرسي مايكل ساكس يأكلون معا، والاستماع إلى بعضهم البعض والتحدث إلى هذا الظن.
وضع هوانغ هاو هذا السؤال بإضافة بصمت الخاصة "قائمة المهام" في.
لحل هذه المشكلة، وهوانغ هاو يفكرون في استخدام نظرية رياضية قبل 200 سنة: ترنحت كوشي نظرية (كوشي نظرية حابك).
هذه النظرية والقيم الذاتية دون مصفوفة لها مرتبطة، مما يجعله أداة مثالية لدراسة العلاقة بين المكعب عالية ومنخفضة الأبعاد. مكعب الأبعاد (مربع) المكعب هو سطح ثلاثي الأبعاد، وبالتالي فإن هذا الأخير هو مجموعة فرعية.
ترنحت كوشي نظرية وذكر على النحو التالي:
A هو ن ن المصفوفة، B هو م أجل م A مصفوفة ماستر (M < ن). A القيم ميزة مصفوفة 1 2 n، حيث مصفوفة B هو 1 2 m، ثم:
وهو قريب من الإجابة، وتقريبا أي شيء على الإطلاق؟ قد يكون من المال.
قررت هوانغ هاو لتقديم طلب للمؤسسة الوطنية للعلوم منح لاستكشاف هذه المسألة.
في الشهر الماضي، وهوانغ هاو يجلس في فندق في مدريد، عند كتابة له طلبات المنح البحثية، انفجار مفاجئ للإلهام: المصفوفة يمكن أن تتغير بعض علامة الرقم، ودفع عملية التصديق حتى النتيجة.
وقال انه بناء مجموعة من 2N 2N مصفوفة النظام، الذي يعرف بأنه:
ويمكن أن يثبت بسهولة عن طريق الاستقراء الرياضي:
وفقا لتعريف القيم الذاتية المصفوفة، القيم الذاتية لو-n n فقط.
عنصر قطري كلها 0، وبالتالي فإن أثر مصفوفة آر (على) = 0. نحن نعلم مصفوفة أثر يساوي مجموع كل القيم الذاتية ، يجب أن يكون عدد يساوي n و-n هي 2N-1 ث.
إذا H هو القمم م FIG (نمط من النقاط والعلاقة بينهما تكوين)، A هو مصفوفة متماثلة، و A هو H من FIG. الجوار مصفوفة .
ما يسمى مصفوفة الجوار، A يشير إلى ش-ث الصف الأول العمود الخامس يمثل ش-عشر عنصرا من الخامس عشر نقطة والنقطة H هي المجاورة، إن لم يكن المجاورة، عنصر يساوي 0، وإذا المجاورة، وهذا العنصر -1 أو 1؛ عنصر قطري بالإضافة إلى ذلك يجب أن يكون مساويا ل0.
من السهل أن تحقق، أمامنا هو هيكل المصفوفة ان ن الأبعاد مكعب QN مصفوفة المجاورة.
FIG فرضية H هو جزء من المكعب ن الأبعاد (وتسمى تحديدا elicitors FIG مكعب QN) ثم H الجوار مصفوفة مصفوفة هناك الرئيسي.
1 افترض هو الحد الأقصى للالقيمة الذاتية للمصفوفة A، ضد هو بالمتجه الذاتي الموافق 1، V1 هو بالمتجه الذاتي من الحد الأقصى للقيمة المطلقة ضد في مكون.
السبب يتم تأسيس مسار الاشتقاق الأول من عدم المساواة المذكورة أعلاه والقيمة المطلقة أقل من المطلق و .
عدم المساواة الثانية هي أيضا في غاية البساطة: (H) هو حساسية الرسم البياني H، في حين أن اليسار هو نقطة حساسة، خريطة حساسية حساسية كبيرة للقيمة الحد الأقصى.
لذلك (H) | 1 |، أي حساسية [دلتا] FIG H (H) أكبر من القيمة المطلقة للمصفوفة كحد أقصى القيمة الذاتية.
و(أ) هو submatrix. إذا احتوى H 2N-1 + 1 القمم معشق في نظرية كوشي:
كما ثبت بالفعل (H) | 1 |، لذلك (H) n، و (H) n هو حساسية بت وظائف منطقية.
وهو المطلوب!
بهذه الطريقة البسيطة، وهوانغ هاو ثبت: أكثر من نصف نقطة في ن الأبعاد مكعب أي مجموعة فرعية، وهناك دائما من توصيل بعض نقطة على الأقل n نقاط أخرى من نفس اللون، فإن النتائج التي يمكن استخلاصها من هذه الحساسية فورا درجة التخمين.
ذيل
واضاف "آمل هوانغ هاو في خريف هذا العام من السيطرة على مجموعة من الدورات الرياضيات تدرس (دليل)، طالما ما يكفي من الدرس."
عندما كلري الوطنية الفرنسية مركز البحث العلمي ماتيو رأى برهان هوانغ هاو، لا يسعه إلا أن تنفس الصعداء عملية التصديق بسيطة.
هوانغ هاو ينتج أكثر من أثبت التخمين حساسية ضروريا، فإنه يجب أيضا أن تنتج أفكارا جديدة في تعقيد التدبير. خوارزميات مثل لالمساواة في السلسلة الثنائية ن بت.
"وتضيف إلى مجموعة من الأدوات التي يمكن أن تساعد لدينا إجابة أسئلة أخرى تحليل وظيفة منطقي"، وقال أستاذ علوم الكومبيوتر في جامعة كولومبيا Servedio، "أعتقد أن الكثير من الناس ينامون في تلك الليلة بعد سماع خبر أسهل."
أنا لا أعرف ما الذي يجعل فجأة كان هوانغ هاو الإلهام، بل أصدقاء ويقول كان هناك احتمال: صندوق الأبحاث الكتابة قد يكون حقا قادرة على تطبيق مساعدة الباحثين ذلك (يضحك).
حول هوانغ هاو
تخرج هوانغ هاو في عام 2007 من قسم الرياضيات، جامعة بكين، وذهب إلى جامعة كاليفورنيا لدراسة، والحصول على شهادة الدكتوراه في الرياضيات في عام 2012، وحصل على درجة أطروحة منحة دراسية سنويا.
بعد تخرجه في معهد الدراسات المتقدمة في جامعة برينستون، معهد الرياضيات، جامعة مينيسوتا عمل أبحاث ما بعد الدكتوراه، بعد دخول قسم الرياضيات في جامعة إيموري كأستاذ مساعد، لديها حول نظرية اندماجي من المجلات الأكاديمية الأخرى نشرت 21 ورقة في مجلة.
الاتجاهات البحثي الرئيسي هوانغ هاو هو مزيج من قيمة متطرفة واحتمال، وهيكل نظرية الرسم البياني، وعلم الحاسوب النظري.
بوابة
أوراق تحتوي على وصلة:
subgraphs الناجم من مكعبات ذات بعد رابع ودليل على حساسية التخمين
https://arxiv.org/abs/1907.00847
- انتهى -
التوظيف الصادق
المكدسة تقوم بتجنيد محرر / مراسل، ومقرها في تشونغ قوان تسون في بكين. نتوقع الموهوبين والطلاب المتحمسين للانضمام إلينا! مزيد من التفاصيل، يرجى و qubit عدد الجمهور (QbitAI) واجهة الحوار والرد "تجنيد" كلمة.
و qubit QbitAI عناوين على التوقيع
' " تتبع تقنيات AI دينامية جديدة والمنتجات
