«Кішкентай» графикалық изоморфизм

Асимметриялық графиктердің изоморфизмін тестілеудің күрделілігі туралы ойланғанда (менің байланысты сұрақты қараңыз менің ойымша қосымша сұрақ пайда болды.

Мысалы, $ 1 ^ n $ кірісінде $ M $ торинг машинасы бар многодинамикалық уақытты $ G_ {M, n} $ $ n $ түйіндерімен жасайды.

$ \ Pi_M $ проблемасын анықтай аламыз:

$ G = (V, E) $ графасын ескере отырып, $ G $ изоморфты $ G_ {M, | V |} $?

Басқаша айтқанда, біз осы графикті бірдей өлшемдегі «анықтамалық» графамен салыстыру керек, ол $ M $ тюринг машинасын тіркелген многочлена уақытпен жасайды.

Барлық многочлена уақытта Торинг машиналары $ M $, бізде $ \ Pi_M \ NP $, ал олардың көпшілігінде $ \ Pi_M \ P $ бар.   Бірақ бұл барлық $ M $ үшін дұрыс? Мәселе белгілі ме?

Бір қарағанда, әрбір $ \ Pi_M $ $ GI $ қарағанда әлдеқайда жеңіл болуы керек деп ойладым, өйткені әрбір $ n $ үшін осы өлшемнің тек бір «сілтеме» кестесі бар және, мүмкін, $ M $ қолданыла алады және тиімді адомодтық изоморфизм тестерлері салынады ... бірақ бұл шындыққа жатпайды: $ M $ $ 1 ^ n $ кірісін (біртұтас) енгізу үшін пайдаланатын әмбебап тайминг машинасын қамтиды мүлдем басқаша (құрылымында) анықтамалық графиктер $ n $ ретінде өседі.

19
«Itsy Bitsy» GI туралы не айтқым келетін M және N үшін біз 1 ^ n-да жасалған екі график бірдей ме, жоқ па деп шешуге тура келеді? (Бұл біртұтас тіл.)
қосылды автор Kev, көзі
Қызықты, сіз P-time Turing машина үлгісін білесіз бе? $ M $, $ G_ {M, N} $?
қосылды автор BlueRaja - Danny Pflughoeft, көзі
TM $ M $ үшін $ G_ {M, n} $ гамильтондық цикл бар деп кепілдік береді, сонда $ \ Pi_M $ $ P $ емес деп ойлаймын.
қосылды автор BlueRaja - Danny Pflughoeft, көзі
G_ {M, n} $ - бұл текше гамильтондық график.
қосылды автор BlueRaja - Danny Pflughoeft, көзі
@ MohammadAl-Turkistany: $ \ Pi_M \ in P $ болатын тривиальды мысал - бұл $ $ n $ оқшауланған шыңдары (немесе біреуі $ K_n $ шығаратын ТМ) шығаратын TM $ M $. Жиынтықты жоғалтпай, сонымен қатар, әр полиномиальды уақытта ТМ екілік алфавит бойынша анықтамалық график жасайды: жай ғана тоқтағаннан кейін таспаның алғашқы $ n ^ 2 $ биттерін таңдап, оны көрші матрица ретінде түсіндіріңіз $ G_ {M, n} $.
қосылды автор Marzio De Biasi, көзі
@ MohammadAl-Turkistany: Менің ойымша, бұл дұрыс емес: тек $ n $ түйіндерінің циклін құрайтын ТМ-ны таңдап алыңыз: барлық $ n $ гамильтон циклы бар анықтамалық графика үшін - полиномиалды уақытта оңай тексеріледі. Мен қарапайым генератордың тривиальды емес мысалын ескеріп отырмын, ол үшін мәселе $ P $ ішінде екенін көрсету өте қиын; бірақ сұраққа қоспас бұрын, мен бірнеше сынақтарды жасаймын.
қосылды автор Marzio De Biasi, көзі
@homtorp: басқа аңдар! :-) ... Мен осы нұсқасында бұл туралы ойладым: $ M_1 $, $ M_2 $ (тіркелген) $ 1 ^ {n ^ 2} $ кірісінде $ A $ бағанға/жол перементтеріне дейін сол матрицаны береді.
қосылды автор Marzio De Biasi, көзі

2 жауаптар

[Бұл жауапқа қарағанда бірнеше кеңейтілген түсініктеме.]

1) $ GI \ notin \ mathsf {P} $ болса, барлық $ \ Pi_ {M} $ уақыттық күрделілігіне байланысты тіркелген многочленность байланысы жоқ, тіпті $ M $ үшін ғана уақытты талап етеді, айталық, $ n ^ 3 $: Егер барлық уақытта - $ n ^ 3 $ $ M $, $ \ Pi_ {M} \ in \ mathsf {DTIME} (n ^ k) $ болса, онда келесі GI үшін поли-уақыттық алгоритм болып табылады. $ M_ (G) $ $ M_ {G} $ $ M_ {G} $ $ M_ {G} $ $ $ n $ 3 $ қадамдармен қамтамасыз ететін сағатты $ $ n $ $ M_ {G} (1 ^ {| V (G) |}) = G $, содан кейін $ \ Pi_ {M_G} (H) $ $ O (n ^ k) $ уақытында шешеді.

2) Себебі кез келген $ M $, $ \ Pi_ {M} $ GI қарағанда қиын, «$ \ Pi_M $ желілері бойынша ең жақсы нәтиже $ \ mathsf {P} «GI толықтығы нәтижесі деп үміттене алады. Дегенмен, менің ойымша, $ \ Pi_M $ кез-келген GI-толық болады, кем дегенде мынадай себептер:

  • Әрбір GI толықтығы нәтижелерін білемін, әр өлшемнің бір графигіне ие емес, жеткілікті үлкен графиктерге арналған. Тиімділік талаптарын толығымен тастасаңыз да, $ G_1, G_2, \ dotsc $ графаларының тізімін білмеймін, бұл $ | V (G_n) | = n $ (немесе тіпті $ poly (n) $), $ G_n $-ға тестілеу изоморфизмі GI-аяқталды.

  • H) $ GI, $ (f (G), f (H)) $ - басқа GI-complet проблемасының мысалы. (Бұл эквиваленттік қатынастардың поли-мезгілдік морфизмдері немесе «Fortnow және I» деп аталатын «ядро қысқарту» деп аталады). Біз сөзсіз түрде оңай көрсете аламыз GI-ден кез келген $ \ Pi_M $ -ға дейін (тіпті бірнеше графиктерді шығаруға $ M $ мүмкіндік беретін анықтаманы өзгерткен болсаңыз да) төмендейді. $ \ {G_ {M, n} \} _ {n \ geq 0} $ ішінде қамтылған.

3) Тіпті осы мәселеде ұсынылған әмбебап ТМ негізіндегі $ M $ құра алатын болса да, мүмкін, тиімді тестерлерді әлі де тиімді түрде құрастыра беруге болады. Яғни, әр $ M $ үшін, $ \ Pi_ {M} $ $ \ mathsf {P/poly} $ болады?

6
қосылды

Менде сіздің сұрағыңызға жауап жоқ, бірақ $ \ Pi_M $ астам шектелген нұсқасын қарастыруға ұсыныс жасаймыз, ол үшін ол P. жатыр.

Графиктердің отбасыларын тек шеттердің саны логарифмдік түрде өсетін етіп қарастырайық. Мәселе тұжырымдамаңызды қайтадан бөліп, оны дұрыс түсіндім ме?

An undirected graph $G$ with $n$ edges can be described by a $\frac{n^2-n}{2}$ long bitstring, simply concatenate the entries of the adjacency matrix of $G$ in the upper triangle. Therefore there are $2^{\frac{n^2-n}{2}}$ possible graphs on $n$ vertices. It follows that any function $f : \mathbb{N} \rightarrow \mathbb{N}$ such that $0 \leq f(n) < 2^{\frac{n^2-n}{2}}$ for all $n$ describes a family of graphs. For any efficiently computable such function $f$ we define $\Pi_f$ as $$ G \in \Pi_f \iff G \text{ is isomorph to the graph described by $f(|V(G)|)$} $$

Табиғи сан үшін $ x $ let $ b_1 (x) $ - екілік көрінісінде 1-ді құрайды. Енді $ \ Pi_f $ ғана қарастырайық тиімді есептеу функциялары үшін $ f $, ол үшін ол $$ b_1 (f (n)) \ in \ mathcal {O} (\ log n) $$ яғни графиктердің отбасы, олар үшін шеттердің саны тек логарифмдік түрде өседі, жоғарыда айтылғандай.

Бұл функциялардың осы сыныптары үшін $ \ Pi_f $ P-де екендігін көрсетеміз.

$ F $ мұндай функция болсын және $ G $ - $ n $ шыңдары бар кіріс кестесі болсын. $ F (n) $ сілтеме сызығына қоңырау шаламыз. Анықтамалық кестеде ең көп $ \ mathcal {O} (\ log n) $ шеттері бар. Осылайша, әрбір МКК (максималды түрде қосылған құрамдас) көптеген $ \ mathcal {O} (\ log n) $ шыңдарынан тұрады, олардың көпшілігі $ n $ болуы мүмкін. Назар аударыңыз, тек $ \ mathcal {O} (\ log n) $ шыңдары бар кез-келген графика үшін, полиномиальдық уақытында изоморфизмді тривиальды түрде тексере аламыз. $ n $, өйткені барлық перестандарттарға әрекет жасай аламыз. Осылайша, кіріс кестесінің әр МК-ні анықтамалық диаграммадағы МКК-ге тағайындау үшін ашуланған алгоритмді қолданып, екі графиктің изоморф болып табылатынын анықтауға болады.

1
қосылды
Шынында да, менің ойымша, оңай дәлел болып табылады. Оны менің жауапыма қосамын.
қосылды автор zetetic, көзі
Сол себепті дәл сол дәлелдер GI үшін жұмыс істейді, бұл шынымен қанағаттанбайды. Менің ойымша, $ \ Pi_f $ параметрінің шеттеріндегі жоғарғы шеттерін жақсартуға болар еді, сондықтан оны жалпы GI үшін жұмысқа ұқсас етіп көрсету мүмкін емес.
қосылды автор zetetic, көзі
Егер сіз өзіңіздің $ f $ -ды жақсы түсінсеңіз, онда шеттердің саны тек логарифмдік түрде өседі. Егер $ G $ эталондық кестеге изоморфалы болса, онда $ n $ болса, оқшауланған шыңдарды кетіру оңай және полиномиальді уақытта сынау. Осылайша, шектелген сынып үшін, P $ \ Pi_ {f} \.
қосылды автор Marzio De Biasi, көзі
Күшті күшті қолданатын дәлел үшін (әр компоненттегі барлық перестандарттар), менің ойымша, сізге $ O (\ log n/\ log \ log n) $ шыңдары үшін әр қосылған құрамдас бөлік қажет: $ (\ log n)! $ негізінен $ (\ log n) ^ {\ log n} = n ^ {\ log \ log n} $. Алайда, $ 2 {{sqrt {v \ log v}} $ уақытты талап ететін ең жақсы белгілі GI алгоритмін пайдаланып $ O (\ log n/\ log \ log n) $ O (\ log ^ 2 n) $.
қосылды автор William S. Godfrey- S.E., көзі