о абстрактном и осязаемом и корне из двух
Jul. 4th, 2002 09:39 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
avvaОчень люблю эту задачку за её неортодоксальное, поразительное своей красотой решение.
Задача: доказать, что существуют два иррациональных числа x и y, так, что xy (икс в степени игрек) - рациональное число.
Решение закрываю элжекатом, но если кто хочет сам подумать, не читайте эту запись дальше пока - в ней оно всё равно обсуждается.
Решение: обозначим sqrt(2) = корень из двух. Рассмотрим число X = sqrt(2)sqrt(2).
Одно из двух: либо X - рациональное число, либо иррациональное.
Если X - рациональное число, то sqrt(2) и sqrt(2) - два иррациональных числа, одно в степени другого дают рациональное, задача решена.
Если X - иррациональное число, то заметим, что X^sqrt(2) = (sqrt(2)sqrt(2))sqrt(2) = sqrt(2)2 = 2. Таким образом, X и sqrt(2) - два иррациональных числа, одно в степени другого дают рациональное - двойку. Задача решена.
Итак, что есть примечательного в этом решении? Мы доказали, что существуют такие иррациональные x и y, что xy - рациональное число. Но мы не показали ни одной такой пары x и y, вообще ни на шаг не приблизились к доказательству того, что вот эти конкретные x и y действительно представляют собой нужную пару.
В принципе понятно, конечно, что наше число X, по-видимому, иррациональное, и, возможно, есть способ это доказать (или нету ещё? я всё время путаюсь в том, что здесь уже умеют делать, а что нет -- кажется, иррациональность epi ещё не доказали, например?). Но в принципе можно себе представить ситуацию, при которой иррациональность или рациональность числа X в принципе были бы недоказуемы; это совсем маловероятно в данном случае, но в каком-нибудь несколько более сложном вполне могло бы такое произойти.
Но даже если бы в принципе невозможно было доказать, что X рационально или что X иррационально -- всё равно наше доказательство оставалось бы верным.
Казалось бы, чего особенного. Подумаешь, доказательство о существовании, не использующее конструктивного построения. Да на каждом шагу в математике. Возьми хоть существование базы у произвольного векторного пространства.
То, да не то. Существование базы требует "мощной" аксиоматической механики - аксиомы выбора. Она изначально и очевидно неконструктивна, затем и нужна. В случае нашей задачки никакой аксиомы выбора не требуется, конструктивность нарушается на гораздо более "примитивном", "осязаемом" уровне - это, может быть, и делает её столь интересной. Мы не привыкли к столь явному нарушению "осязаемости" в столь простых вещах. Нам хочется взять и "пощупать" руками наши x и y, но мы не можем.
Математик-интуиционист, последователь Брауэра, назвал бы наше доказательство неприемлемым, неверным. Проблема его не в том даже, что доказывается существование чего-то без того, чтобы привести конкретный пример. Принципы интуиционизма (а вслед за ним конструктивизма) допускают, например, конструктивные доказательства от обратного. Если бы мы предположили, что таких x и y не существует, и это предположение смогли бы конструктивным путём привести к противоречию - это было бы приемлемое с точки зрения строгого интуициониста доказательство.
Проблема в другом: в использовании принципа исключённого третьего без конструктивного его разрешения. Мы говорим: либо X рационально, либо нет. Для математика-интуициониста это утверждение имеет смысл только в том случае, когда мы можем собственно описать какую-то процедуру, позволяющую нам решить, рационально X или нет. Мы не можем разбить решение на два случая (соответствующие рациональности и иррациональности X), не давая при этом возможности решить, какой из них "в действительности" верен (и, более того, допуская, что этот вопрос в принципе может оказаться нерешаемым!).
Все эти претензии математика-интуициониста практических последствий не имеют, просто потому, что математиков-интуиционистов уже много лет как нет (а горстка конструктивистов никакой значительной роли не играет). В математике победил торжествующий платонизм, а интуиционизм изучается философами и логиками, но не используется в своей повседневной работе математиками. Я отнюдь не пытаюсь утверждать, что приведенное выше доказательство существования x и y действительно неверно или неприемлемо.
Но претензии эти, придирки гипотетического интуициониста на самом деле полезны: они помогают нам понять, что нам кажется странным, неординарным в этом доказательстве. Вот это, действительно, и кажется - это торжествующе-неконструктивное применение принципа исключённого третьего (который, напомню, гласит: "либо A, либо не-А"; "третьего" не дано).
В случае нашей задачки это скорее курьёз, забавная штука. Несколько по-другому выходит, когда речь заходит о теории вычислимости, алгоритмах, машинах Тюринга и т.п. Мне кажется, что там, или по крайней мере в философии вычислимости, вопрос конструктивности становится более релевантным, более неотложным.
Вот простой пример. Возьмём какой-то нерешённый математикой вопрос. Например:
Верно ли то, что любое чётное число может быть представлено в виде суммы двух простых чисел?
Обозначим утверждение любое чётное число может быть представлено в виде суммы двух простых чисел буквой G. Теперь спросим следующее:
1. Существует ли машина Тюринга (иными словами, алгоритм), который выдаёт на выходе 1, если гипотеза G верна, и 0, если она неверна?
Казалось бы, задать этот вопрос - всё равно, что спросить "можем ли мы решить G алгоритмическим путём?" Но выясняется что это не так. Оказывается, существует тривиальный положительный ответ на вопрос 1.:
Если G верна, то возьмём в качестве нашей машины Тюринга машину, которая пишет в качестве вывода 1 и останавливается.
Если G неверна, то возьмём в качестве нашей машины Тюринга машину, которая пишет в качестве вывода 0 и останавливается.
В любом случае, существует машина Тюринга, к-я пишет 1, если G верна, и 0, если G неверна.
Мы ощущаем, что такое "решение" является обманом, подлогом. Но почему? Что здесь происходит? Что не так?
Легко увидеть аналогию с доказательством задачки про иррациональные числа. Мы не знаем, верна G или нет. Но если она верна, то мы можем сделать так-то, а если неверна, то по-другому. В результате мы получаем вполне правильное доказательство существования искомой машины, которое, тем не менее, совершенно нас не устраивает.
Проблема в том, что мы отождествляем понятия "существует алгоритм, который делает X" и "мы можем решить X алгоритмическим путём". Вышеизложенный подлог как раз и показывает, что это одождествление неправомочно. Нам недостаточно знать о существовании алгоритма; нам нужно держать "в руках" сам алгоритм.
Нам нужно конструктивное доказательство того, что существует алгоритм, решающий проблему G, и только такое доказательство мы примем в качестве верного. Неконструктивное доказательство формально верно, но мы отметаем его как бесполезное, обманное. Ситуация здесь полностью противоположна ситуации с числами.
Но вот формально выразить это "держать в руках" оказывается делом непростым. С точки зрения формальной математики мы можем пользоваться квантором существования и всё. Не поможет и мета-переход внутри самой теории вычислимости, хотя на первый взгляд он мог бы быть полезен. Мы могли бы попробовать сказать следующее: мы можем алгоритмически решить проблему G если не просто существует машина Тюринга, дающая на неё правильный ответ, а кроме того, существует другая машина Тюринга, эту первую машину правильно распознающая: говорящая нам, когда мы имеем дело с ней, а когда с какой-то другой машиной, G не решающей. Но увы, этот трюк только отодвигает некоструктивность на один уровень выше: тогда эта самая мета-машина будет существовать, но будет разной в зависимости от того, верна G или нет.
Возможно, действительно стоит попробовать подойти к теории вычислимости с точки зрения интуициониста, возможно, даже с формальным набором интуиционистской логики и методологии. Действительно ли это поможет? не знаю, и, честно говоря, сомневаюсь. Но что тогда вместо этого?
Над этим вопросом - конструктивизма в теории вычислимости, над тем, что означает в разных контекстах задать алгоритм, над разницей между существованием и "держанием в руках" - я размышляю уже больше года (не всё время, конечно - время от времени), в разных аспектах и под разными углами. Время от времени мне кажется, что я вижу что-то, какой-то многообещающий подход, нечто интересное, позволяющее подойти к этой проблеме несколько по-другому... но ни разу ничего конкретного мне получить так и не удалось.
Задача: доказать, что существуют два иррациональных числа x и y, так, что xy (икс в степени игрек) - рациональное число.
Решение закрываю элжекатом, но если кто хочет сам подумать, не читайте эту запись дальше пока - в ней оно всё равно обсуждается.
Решение: обозначим sqrt(2) = корень из двух. Рассмотрим число X = sqrt(2)sqrt(2).
Одно из двух: либо X - рациональное число, либо иррациональное.
Если X - рациональное число, то sqrt(2) и sqrt(2) - два иррациональных числа, одно в степени другого дают рациональное, задача решена.
Если X - иррациональное число, то заметим, что X^sqrt(2) = (sqrt(2)sqrt(2))sqrt(2) = sqrt(2)2 = 2. Таким образом, X и sqrt(2) - два иррациональных числа, одно в степени другого дают рациональное - двойку. Задача решена.
Итак, что есть примечательного в этом решении? Мы доказали, что существуют такие иррациональные x и y, что xy - рациональное число. Но мы не показали ни одной такой пары x и y, вообще ни на шаг не приблизились к доказательству того, что вот эти конкретные x и y действительно представляют собой нужную пару.
В принципе понятно, конечно, что наше число X, по-видимому, иррациональное, и, возможно, есть способ это доказать (или нету ещё? я всё время путаюсь в том, что здесь уже умеют делать, а что нет -- кажется, иррациональность epi ещё не доказали, например?). Но в принципе можно себе представить ситуацию, при которой иррациональность или рациональность числа X в принципе были бы недоказуемы; это совсем маловероятно в данном случае, но в каком-нибудь несколько более сложном вполне могло бы такое произойти.
Но даже если бы в принципе невозможно было доказать, что X рационально или что X иррационально -- всё равно наше доказательство оставалось бы верным.
Казалось бы, чего особенного. Подумаешь, доказательство о существовании, не использующее конструктивного построения. Да на каждом шагу в математике. Возьми хоть существование базы у произвольного векторного пространства.
То, да не то. Существование базы требует "мощной" аксиоматической механики - аксиомы выбора. Она изначально и очевидно неконструктивна, затем и нужна. В случае нашей задачки никакой аксиомы выбора не требуется, конструктивность нарушается на гораздо более "примитивном", "осязаемом" уровне - это, может быть, и делает её столь интересной. Мы не привыкли к столь явному нарушению "осязаемости" в столь простых вещах. Нам хочется взять и "пощупать" руками наши x и y, но мы не можем.
Математик-интуиционист, последователь Брауэра, назвал бы наше доказательство неприемлемым, неверным. Проблема его не в том даже, что доказывается существование чего-то без того, чтобы привести конкретный пример. Принципы интуиционизма (а вслед за ним конструктивизма) допускают, например, конструктивные доказательства от обратного. Если бы мы предположили, что таких x и y не существует, и это предположение смогли бы конструктивным путём привести к противоречию - это было бы приемлемое с точки зрения строгого интуициониста доказательство.
Проблема в другом: в использовании принципа исключённого третьего без конструктивного его разрешения. Мы говорим: либо X рационально, либо нет. Для математика-интуициониста это утверждение имеет смысл только в том случае, когда мы можем собственно описать какую-то процедуру, позволяющую нам решить, рационально X или нет. Мы не можем разбить решение на два случая (соответствующие рациональности и иррациональности X), не давая при этом возможности решить, какой из них "в действительности" верен (и, более того, допуская, что этот вопрос в принципе может оказаться нерешаемым!).
Все эти претензии математика-интуициониста практических последствий не имеют, просто потому, что математиков-интуиционистов уже много лет как нет (а горстка конструктивистов никакой значительной роли не играет). В математике победил торжествующий платонизм, а интуиционизм изучается философами и логиками, но не используется в своей повседневной работе математиками. Я отнюдь не пытаюсь утверждать, что приведенное выше доказательство существования x и y действительно неверно или неприемлемо.
Но претензии эти, придирки гипотетического интуициониста на самом деле полезны: они помогают нам понять, что нам кажется странным, неординарным в этом доказательстве. Вот это, действительно, и кажется - это торжествующе-неконструктивное применение принципа исключённого третьего (который, напомню, гласит: "либо A, либо не-А"; "третьего" не дано).
В случае нашей задачки это скорее курьёз, забавная штука. Несколько по-другому выходит, когда речь заходит о теории вычислимости, алгоритмах, машинах Тюринга и т.п. Мне кажется, что там, или по крайней мере в философии вычислимости, вопрос конструктивности становится более релевантным, более неотложным.
Вот простой пример. Возьмём какой-то нерешённый математикой вопрос. Например:
Верно ли то, что любое чётное число может быть представлено в виде суммы двух простых чисел?
Обозначим утверждение любое чётное число может быть представлено в виде суммы двух простых чисел буквой G. Теперь спросим следующее:
1. Существует ли машина Тюринга (иными словами, алгоритм), который выдаёт на выходе 1, если гипотеза G верна, и 0, если она неверна?
Казалось бы, задать этот вопрос - всё равно, что спросить "можем ли мы решить G алгоритмическим путём?" Но выясняется что это не так. Оказывается, существует тривиальный положительный ответ на вопрос 1.:
Если G верна, то возьмём в качестве нашей машины Тюринга машину, которая пишет в качестве вывода 1 и останавливается.
Если G неверна, то возьмём в качестве нашей машины Тюринга машину, которая пишет в качестве вывода 0 и останавливается.
В любом случае, существует машина Тюринга, к-я пишет 1, если G верна, и 0, если G неверна.
Мы ощущаем, что такое "решение" является обманом, подлогом. Но почему? Что здесь происходит? Что не так?
Легко увидеть аналогию с доказательством задачки про иррациональные числа. Мы не знаем, верна G или нет. Но если она верна, то мы можем сделать так-то, а если неверна, то по-другому. В результате мы получаем вполне правильное доказательство существования искомой машины, которое, тем не менее, совершенно нас не устраивает.
Проблема в том, что мы отождествляем понятия "существует алгоритм, который делает X" и "мы можем решить X алгоритмическим путём". Вышеизложенный подлог как раз и показывает, что это одождествление неправомочно. Нам недостаточно знать о существовании алгоритма; нам нужно держать "в руках" сам алгоритм.
Нам нужно конструктивное доказательство того, что существует алгоритм, решающий проблему G, и только такое доказательство мы примем в качестве верного. Неконструктивное доказательство формально верно, но мы отметаем его как бесполезное, обманное. Ситуация здесь полностью противоположна ситуации с числами.
Но вот формально выразить это "держать в руках" оказывается делом непростым. С точки зрения формальной математики мы можем пользоваться квантором существования и всё. Не поможет и мета-переход внутри самой теории вычислимости, хотя на первый взгляд он мог бы быть полезен. Мы могли бы попробовать сказать следующее: мы можем алгоритмически решить проблему G если не просто существует машина Тюринга, дающая на неё правильный ответ, а кроме того, существует другая машина Тюринга, эту первую машину правильно распознающая: говорящая нам, когда мы имеем дело с ней, а когда с какой-то другой машиной, G не решающей. Но увы, этот трюк только отодвигает некоструктивность на один уровень выше: тогда эта самая мета-машина будет существовать, но будет разной в зависимости от того, верна G или нет.
Возможно, действительно стоит попробовать подойти к теории вычислимости с точки зрения интуициониста, возможно, даже с формальным набором интуиционистской логики и методологии. Действительно ли это поможет? не знаю, и, честно говоря, сомневаюсь. Но что тогда вместо этого?
Над этим вопросом - конструктивизма в теории вычислимости, над тем, что означает в разных контекстах задать алгоритм, над разницей между существованием и "держанием в руках" - я размышляю уже больше года (не всё время, конечно - время от времени), в разных аспектах и под разными углами. Время от времени мне кажется, что я вижу что-то, какой-то многообещающий подход, нечто интересное, позволяющее подойти к этой проблеме несколько по-другому... но ни разу ничего конкретного мне получить так и не удалось.
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
no subject
Date: 2002-07-04 11:57 am (UTC)2. Знаете ли Вы такого конструктивистского философа математики (и других предметов) по имени Paul Lorenzen (Пауль Лоренцен, наверное, т.к. он был немец)?
no subject
Date: 2002-07-04 12:17 pm (UTC)http://mathworld.wolfram.com/IrrationalNumber.html
http://mathworld.wolfram.com/TranscendentalNumber.html
(С извинениями за удаленный коммент, т.к.слишком много опечаток.)
no subject
Date: 2002-07-04 12:18 pm (UTC)Как насчет e**(ln(2)) = 2?
no subject
Date: 2002-07-04 12:37 pm (UTC)no subject
Date: 2002-07-04 12:44 pm (UTC)no subject
Date: 2002-07-04 12:54 pm (UTC)no subject
Date: 2002-07-04 01:06 pm (UTC)Сама теорема говорит что для любого конечного множества алгебраических чисел линейно независимых над полем рациональных чисел их экспоненты алгебраически независимы.
Я когда-то знал, как она доказывается.
no subject
Date: 2002-07-04 01:07 pm (UTC)Поправка-следует читать
Date: 2002-07-04 01:10 pm (UTC)no subject
no subject
Date: 2002-07-04 01:17 pm (UTC)XXX = 1, если царевич Димитрий был убит
ХХХ = 0, если царевич Димитрий сам убился
Решим историко–математическую задачу: найдите х, если
х + ХХХ = 2 + ХХХ
Решение:
х = 2 (но мы так и узнали что же случилось с Димочкой)
Разве ХХХ не аналогично вашему Х из решения задачи? Как на это поглядит математик-интуиционист (а равно и прочие подвиды математиков)?
no subject
Date: 2002-07-04 01:51 pm (UTC)no subject
Date: 2002-07-04 02:00 pm (UTC)no subject
Date: 2002-07-04 02:01 pm (UTC)no subject
Date: 2002-07-04 02:02 pm (UTC)no subject
Date: 2002-07-04 02:06 pm (UTC)И вообще, если у Вас есть мнение по всему этому поводу, поделитесь. А то многие оставили мелкие комменты по частностям, но мне интересно было бы узнать общее мнение по сути.
no subject
Date: 2002-07-04 02:09 pm (UTC)Нет, ведь XXX не использовался никаким реальным образом в "решении" уравнения. Собственно, решение уравнения не использует принцип исключённого третьего. X, с другой стороны, активно участвует в решении каждого случая в отдельности (и поэтому необходимо использовать исключённое третье).
К тому же определение XXX совершенно неформализуемо, в отличие от X. Не думаю, что какому-либо математику очень интересно XXX и что с ним происходит.
no subject
Date: 2002-07-04 02:36 pm (UTC)Мы знаем, что sqrt2 иррационально. Вы говорите: возьмем конкретное число Х = sqrt2 ** sqrt2. Мы не знаем, рационально ли оно. Но если оно иррационально, то Х**sqrt2 –– рационально.
Вы видите в этом какую–то тонкость (математическую или философскую) которую я не улавливаю, сколько я не перечитываю.
Re:
Date: 2002-07-04 02:45 pm (UTC)Ну как, X ведь является частью решения.
Вы видите в этом какую–то тонкость (математическую или философскую) которую я не улавливаю, сколько я не перечитываю.
Философскую, несомненно. У нас есть утверждение: "Либо X рационально, либо X иррационально". Это утверждение есть пример принципа исключённого третьего. В данном случае, однако, интуиционизм запрещает использовать такое утверждение внутри доказательства, если у нас нет никакого эффективного способа решить, какая из двух альтернатив имеет место.
Далее, как следствие применения этого принципа в данном случае, наше доказательство получается неконструктивным. Мы знаем, что есть x и y, но не знаем, какие они; может быть, sqrt(2) и sqrt(2), а может быть, X и sqrt(2). Это очень люпобытный случай локализованной неконструктивности. Сравните его, например, с двумя разными доказательствами существования иррациональных чисел вообще:
1. Берём sqrt(2), доказываем, что оно иррационально, всё.
2. Пересчитываем рациональные числа - их алеф-0, а всех действительных 2^алеф-0, поэтому должны быть иррациональные.
Второе док-во неконструктивно (не даёт нам ни одного иррационального числа). Но это более привычный вид неконструктивности, нежели в случае X. Вот если бы док-во выглядело так: мы находим два числа a и b, и доказываем что одно из них обязано быть иррациональным, но мы не знаем точно, какое из двух - это было бы похожим на случай с X. Но такое вообще редко встречается.
no subject
Date: 2002-07-04 02:59 pm (UTC)no subject
Date: 2002-07-04 03:22 pm (UTC)Я видимо очень математически толстокожий человек, т.к. ощущаю одинаковый комфорт от доказательств 1 и 2. На вопрос ответил: "иррациональные числа –– их есть," и ушел.
Я даже не подозревал, что неконструктивные доказательства чем–то хуже (или необычней) конструктивных.
Фразу "могу доказать что оно есть, но я его не знаю" произношу без дрожи в голосе.
Также спокойно как и фразу "решение этой задачи –– А или Б, и ничто другое; но А оно или Б –– об этом математики еще не додумались, так как не знают верно ли заявление ХХХ" если я "вижу", что заявление ХХХ (например, "число Х –– рационально") никаких "геделевских" проблем не создает. А если ХХХ создает "геделевские" проблемы, то и сама задача сводится к неразрешимости (будь ты хоть конструктивист, хоть интуитивист, хоть кто).
Ну и что же мне эти проклятые интуитивисты запретить хотят?:)
Re:
Date: 2002-07-04 03:34 pm (UTC)То, что у Вас не возникает никаких проблем от неконстурктивных доказательств, всего лишь говорит о том, что Вы - платонист. Ну и ладно, я тоже платонист. Вообще почти все действующие сегодня математики тоже платонисты (обычно наивные, т.е. не задумывающиеся об этом). Для меня тоже 2 вполне нормально док-во. Я ощущаю разницу между 2 и 1, но не в том смысле, чтобы считать 2 худшим или неверным, а только для изучения разных видов доказательств, для мета-математических целей.
Но во второй части моей записи, мне кажется, я привёл достаточно убедительный случай, когда это действительно оказывается важным - пример неконструктивного "алгоритма", который мы интуитивно не воспринимаем в качестве "правильного" решения. Т.е. волей-неволей нам приходится, если мы хотим понять, откуда берутся такие случаи, вернуться к конструктивистской терминологии и, в частности, проводить различие между "существованием алгоритма" и "нашим знанием алгоритма".
Мне так, по крайней мере кажется. Я не убеждён в том, что я прав. Но в любом случае это не просто исторический дискурс в интуиционизм, а попытка понять философские аспекты некоторых ситуаций, которые (в теории вычислимости и алгоритмов) обычно игнорируют или заметают под ковёр.
no subject
Date: 2002-07-06 08:55 am (UTC)AI
Date: 2002-07-08 02:11 am (UTC)Есть книжечка, претендующая на место современной Алисы (зазеркалье): "Гёдель, Эшер, Бах: вечная золотая цепь". Там практикующий программист просто прёт, как Бегемот.
Издана в US, где-то в семидесятых(?).
Re: AI
Date: 2002-07-08 02:16 am (UTC)А GEB я тоже хорошо знаю, спасибо.
Голем 44 (ГСЧ(RND))
Date: 2002-07-08 02:37 am (UTC)анонимнай эпылог
Date: 2003-11-10 03:18 am (UTC)и обернись лицом глазами назад раз-за-за-раз№ум
увидишь вееерштрасеры летят
и пролетают мимо пьюли
штрассссёров всех пересъедали мысь
и объядали и обласкивали були
и буля ка-то-1-то как Тараз
назвался не буляускас а был ли
и маков-маков-маков-ЦВЁЛ
и заОлелись розовым нам ГУбы
и будет иль здесь
иль не почём
и как то раз мы не свернули
шёл в комнату, попал в другую
Date: 2013-02-04 02:51 pm (UTC)"Неконструктивное" доказательство, конечно, красиво, но есть и "явное", на школьном уровне, не ссылающееся при этом ни на Гельфонда, ни на другие сложные результаты. Тут, конечно, достаточно логарифмов типа log2(3), где иррациональность равносильна очевидному факту, что 2m не равно 3n (гораздо проще "корня из двух"!). А далее берём x=21/2, и возводим в степень y=2*log2(3), получая в итоге 3.
no subject
Date: 2016-09-11 07:03 pm (UTC)Нил Робертсон и Пол Сеймур с 1984 по 2012 год публиковали серию из 23 статей про теорию графовых миноров. Минор - это граф, который можно получить из исходного удалением и стягиванием рёбер. Среди прочих фактов в их статьях есть такие две теоремы:
- распознать наличие данного графа среди миноров можно за полиномиальное время
- если некоторое свойство сохраняется при удалении и стягивании рёбер, то есть лишь конечное число запрещённых миноров: если их в графе нет, то свойство выполняется. Примеры свойств: вложимость в плоскость (т.е. планарность) или другую двумерную поверхность, возможность размещения в пространстве с незаузленными и/или незацепленными циклами и т.д. Ранее это утверждение было известно как гипотеза Вагнера.
В сумме эти два утверждения дают существование полиномиального алгоритма для любых подобных свойств. Вот только откуда брать список запрещённых миноров? Для свойства планарности они всем известны: K_5 и K_3,3. А вот уже для вложимости в тор полного списка нет. Получается, есть целый класс задач, для которых есть полиномиальный алгоритм, а какой именно, неизвестно.
no subject
Date: 2016-09-11 07:10 pm (UTC)