4551
правка
Цветовое кодирование: различия между версиями
Перейти к навигации
Перейти к поиску
м
→Открытые вопросы
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 50: | Строка 50: | ||
== Открытые вопросы == | == Открытые вопросы == | ||
Перечисленные ниже задачи все еще остаются нерешенными. | Перечисленные ниже задачи все еще остаются нерешенными. | ||
• Существует ли (детерминированный или рандомизированный) алгоритм с полиномиальным временем выполнения, определяющий, содержит ли заданный граф G = (V, E) путь длины, скажем, | |||
• Существует ли (детерминированный или рандомизированный) алгоритм с полиномиальным временем выполнения, определяющий, содержит ли заданный граф G = (V, E) путь длины, скажем, <math>log^2 \; |V|</math>? (Это маловероятно, поскольку в таком случае должен был бы существовать алгоритм, за время <math>2^{O(\sqrt{n})}</math> определяющий, является ли заданный граф с n вершинами Гамильтоновым). | |||
• Можно ли отбросить коэффициент log |V|, появляющийся в процессе дерандомизации? | • Можно ли отбросить коэффициент log |V|, появляющийся в процессе дерандомизации? | ||
• Имеют ли задача определения, содержит ли заданный граф G = (V, E) треугольник, и задача | |||
• Имеют ли задача определения, содержит ли заданный граф G = (V, E) треугольник, и задача булева умножения двух матриц |V| x |V| равными по сложности? | |||
== Экспериментальные результаты == | == Экспериментальные результаты == | ||