Cтраница 2
Вопрос о том, когда два стационарных источника изоморфны, эквивалентен проблеме изоморфизма динамических систем в эргодической теории. Колмогоров доказал утверждение ( с) и, опираясь на него, доказал - решив долго остававшуюся открытой проблему, - что два ДИБП, порождающие распределения которых имеют различные энтропии, не могут быть изоморфными. В знаменитой теореме Орн-стейна ( Ornstein ( 1970)) доказано, что для ДИБП равенство энтропии порождающих распределений влечет за собой изоморфизм. [16]
Отметим, что именно эта задача была сведена в работе [8] к проблеме изоморфизма конических графов. [17]
Задача о том, определяют ли два разных копредставления изоморфные группы, называется проблемой изоморфизма. Общее решение этой проблемы не существует1), но можно найти весьма важные для нас частные решения. [18]
Мы встречаемся здесь с примером, когда содержательный топологический вопрос приводит к частному случаю проблемы изоморфизма. [19]
Проблема изоморфизма любой данной конечно определенной группе неразрешима ( теорема Адяна), Вопрос о разрешимости проблемы изоморфизма в классе групп с одним соотношением открыт. [20]
Подробное изображение химических структур, участвующих в каталитическом процессе, их однозначное кодирование тесно связано с проблемой изоморфизма, с теоретико-графовыми и топологическими представлениями. [21]
Получение искусственных асбестов представляет большой научный интерес для решения ряда теоретических вопросов физической химии силикатов, физики твердого тела, генетической минералогии, связанных с проблемами изоморфизма в сложных по составу силикатах, механизмом п кинетикой кристаллизации волокнистых кристаллов ( вискерсов), их прочностными свойствами, проблемой генезиса асбеста в природных условиях и другими вопросами. [22]
Если мы рассмотрим еще большие группы, такие как симметрическая группа Sn или общая линейная группа GLn, то проблема эквивалентности многочленов относительно такой группы является универсальной по отношению к проблеме изоморфизма графов: в случае группы Sn это очевидно уже для многочленов степени 2, в случае GLn это было замечено А. [23]
Для того, чтобы локазать, что тавтологии Р - сводится к простые числа, по-видимому, требуются некоторые глубокие результаты из теории чисел, в то время как доказательство того, что тавтологии Р - сводится к пара изомбрфных графов, вероятно, послужит опровержению одной гипотезы Корнеля [4], из которой он выводит, что проблема изоморфизма графов может быть решена за полиномиальное время. [24]
Пусть Ж - рекурсивно перечислимый класс конечных групповых кодов, 3: 5f - - N - инъективная геде-лева нумерация кодов из Ж и М - подмножество N X N, состоящее из всех таких пар ( k i), для которых коды - l ( k) и Р - ( /) определяют изоморфные группы. Проблема изоморфизма для класса Ж разрешима в том и только в том случае, когда множество М является рекурсивным. [25]
Пусть Ж - рекурсивно перечислимый класс конечных групповых кодов, Р: Jf-N - инъективная геде-лева нумерация кодов из Ж и М - подмножество N N, состоящее из всех таких пар ( k, l), для которых коды - l ( k) и P - - ( 0 определяют изоморфные группы. Проблема изоморфизма для класса Ж разрешима в том и только в том случае, когда множество М является рекурсивным. [26]
Как было замечено в главе 5, каждая конечно представленная группа реализуется в виде фундаментальной группы 4-мно-гообразия. Этот факт вместе с неразрешимостью проблемы изоморфизма был использован А. А. Марковым [15] для доказательства алгоритмической неразрешимости проблемы изоморфизма для 4-многообразий. Работа Маркова была последовательно обобщена Буном, Хакеном и Поенарю [37] на диффео-морфную, а также комбинаторную эквивалентность. В отличие от того, что возникает при работе с группами, в данном случае некоторое внимание должно быть обращено на описание многообразия, к которому применяются критерии проблемы разрешения. [27]
После того, как было получено представление с неразрешимой проблемой слов, оказалось возможным доказать алгоритмическую неразрешимость некоторых других проблем. Наиболее примечательная из них - поставленная Дэном проблема изоморфизма, неразрешимость которой доказали С. И. Адян [2], а после него Рабин [160] следующим способом. [28]
Такие условия весьма важны, так как они позволяют устанавливать, что те или иные группы неизоморфны. Далее будут рассмотрены методы нахождения подобных частных решений проблемы изоморфизма. [29]
Восстановление связано с рассмотрением классов изоморфизма. Занимаясь задачами восстановления, мы неизбежно приходим к проблеме изоморфизма, состоящей в выяснении того, изоморфны или нет два заданных графа. Автор не очень сведущ в алгоритмической тематике, но он знает, что хорошего алгоритма для проблемы изоморфизма пока неизвестно, и предполагает, что такого алгоритма вообще не существует. [30]