On symmetric and choiceless computation (کنفرانس TTCS)

Mechanization of Abstraction (Aho, Ullman)

تطابق دوبخشی با الگوریتم مسیر افزایشی به دلیل انتخاب دلخواهی که انجام می‌دهد، تقارن را رعایت نمی‌کند. {و حالا در ادامه می‌گوییم که چرا این بد است!}

کلاس FPC:

شبیه ماشین تورینگ اما با جدولی مانند پایگاه داده یک ماشین می‌سازیم به نام ماشین رابطه‌ای (relational machine) که در زمان چندجمله‌ای مسایل کلاس FP<P را تصمیم می‌گیرد. انواع مختلفی از این ماشین هست:

abiteboul, vardi, .. + counting

هدف ما اینجا این است که نتیجه فقط به توپولوژی بستگی داشته باشند و نه نام‌گذاری.

P-Complete < FPC

در سال ۲-۱- Grohe ثابت کرد که مسایل P که proper minor-closed class of graph هستند زیرمجموعه‌ی FPC هستند.

LPها (برنامه‌ریزی خطی) زیرمجموعه‌ی FPC هستند.

آنهایی که CFI property را دارند زیرمجموعه‌ی P هستند اما زیرمجموعه‌ی FPC نیستند. {در نتیجه P و FPC یکی نیستند.}

*Abstract state machineها از ماشین‌های رابطه‌ای قوی‌تر هستند چون اجازه‌ی مواردی مانند مجموعه‌ها، مجموعه‌ای از مجموعه‌ها و .. را می‌دهند. این ماشین‌ها در زمان چندجمله‌ای مسایلی را تصمیم‌گیری می‌کنند که به آنها Choiceless Polynomial Time می‌گویند.  زمان این ماشین با تعداد گام‌های آن اندازه‌گیری می‌شود و حافظه‌ی آن با تعداد مجموعه‌ها.

می‌دانیم FPC < CPT است اما نمی‌دانیم چه رابطه‌ای با P دارد.

*مدارها برای مسایل گراف (Circuits for graph problems)

گراف با ماتریس مجاورت آن داده می‌شود. چیزی به نام Invariant Circuits داریم که جایگشت دادن رأسهای ورودی، خروجی را تغییر نمی‌دهد. پس FPCها زیرمجموعه‌ی این کلاس هستند.

* Polynomial Time Graph Properties

با مدارهای متقارن که زیرمجموعه‌ی مدارهای invariant هستند می‌شود تشخیص داد. مثالی از مداری که متقارن نیست اما invariant هست مدل آبشاری (اگر اسمش را اشتباه نگویم) است که در آن مثلاً برای به دست آوردن or همه خروجی قبلی‌ها را با عدد بعدی می‌گیریم. (یک درخت با ارتفاع n)

جایگشت‌هایی که گیت g را به خودش می‌برند را stabilizer group of g می‌نامیم.

تعداد مدارهای متقارن برابر است با:

n! / |stab(g)|

* مسئله‌ی pebble game (bijection game) در سال ۹۶ توسط Hella

* 3-SAT عضو FPC نیست (با CFI ثابت می‌شود).

این نتایج هیچ فرضی برای P vs. NP نیاز ندارند.

یک سری لیست مطالب هم هست که چون در پست‌های قبلی اسلاید اصلی ارائه هست دوباره نمی‌نویسم. مثلاً ۲-رنگ پذیری در این کلاس هست اما ۳-رنگ پذیری نیست. ۲-sat هست اما 3-sat نیست. ...

سوالی که من پرسیدم که چه کتابی در مورد این هست یک کتاب ۱۹۹۹ معرفی کردند که در کتابچه‌ی TTCS هست.