Теория сложности.

[akram_jadid]

Хочу узнать определение понятия "сложность" или "степень сложности" выраженное в математических категориях.
ну ребята? есть какие-нить идейки?

[Brukvalub]

???

akram_jadid в сообщении #140542 писал(а):

Хочу узнать определение понятия "сложность" или "степень сложности" выраженное в математических категориях.
ну ребята? есть какие-нить идейки?

У Колмогорова: http://teormin.ifmo.ru/education/intro/ ... exity.html была идейка. А так - полный тупик ???

[маткиб]

А какая собственно сложность интересует? И сложность чего?

Традиционно рассматривают:

1) Сложность бесконечных объектов, например, функций на множестве натуральных чисел. Рассматривают сложность либо с точки зрения вычисления, либо с точки зрения описания. Если с точки зрения вычисления - то обычно говорят о принадлежности объекта сложностному классу, потому что определить сложность как число или функцию не удаётся. Например, самый часто встречающийся в литературе класс P - класс функций, для которых существует алгоритм (машина Тьюринга), вычисляющая данную функцию за время, не превосходящее полинома от длины записи аргумента. Сложность с точки зрения описания - минимальная длина описания функции в каком-либо формализме. Например, минимальный размер вычисляющей программы (по колмогорову).

2) Сложность конечных объектов (например, булевых функций или наборов из нулей и единиц). Определяют обычно как минимальную длину реализующей булевой формулы или схемы из функциональных элементов в некотором базисе (например, {AND, OR, NOT}). В этом случае сложность имеет смысл и как сложность вычисления, и как сложность описания. Кроме этого, можно и по Колмогорову.

3) Сложность математических утверждений - минимальная длина доказательства в некотором формализме. Часто рассматривают для пропозициональных тавтологий.

Короче, формализаций много, и в каждом случае результат получается свой (как и применение). Поиск в интернете по ключевым словам должен дать много интересного (если нужны подробности).

[akram_jadid]

Почти во всех источниках дается определения сложности в частных случаях. Напр.: сложность алгоритмов, сложность вычесления и т.д...
Я, в процесе построения ряда логических цепочек столкнулся с необходимостью определения понятия сложности. И естественно с необходимостью определения понятия "степень сложности". Что мы понимаем под словом "сложность" ? Этот вопрос я задал кондидату технических наук, и удовлитворительного ответа не получил....
Я пытаюсь решить очень сложную матеметическую задачу, которое пока что путем вычеслений решить не удается. Вы все слижком углубились в какой то области, и не видите дальше носа...
Правда, я сам попытался опредилить что такое сложность. Для этого мне пришлось ввести новое понятия, новый термин "количество знания". Если кто то откликнется, я готов обсудить свои идеии...

[SAN_666]

Сложность - субъективное понятие, которым пользуются любители математики, и только они.

[Anton Nonko]

akram_jadid писал(а):

Почти во всех источниках дается определения сложности в частных случаях. Напр.: сложность алгоритмов, сложность вычесления и т.д...
Я, в процесе построения ряда логических цепочек столкнулся с необходимостью определения понятия сложности. И естественно с необходимостью определения понятия "степень сложности". Что мы понимаем под словом "сложность" ? Этот вопрос я задал кондидату технических наук, и удовлитворительного ответа не получил....
Я пытаюсь решить очень сложную матеметическую задачу, которое пока что путем вычеслений решить не удается. Вы все слижком углубились в какой то области, и не видите дальше носа...
Правда, я сам попытался опредилить что такое сложность. Для этого мне пришлось ввести новое понятия, новый термин "количество знания". Если кто то откликнется, я готов обсудить свои идеии...

В разных областях понятие сложности может иметь совсем различные интерпретации. Можно считать это омонимом. Если Вы пытаетесь определить "сложность вообще", то это, скорее всего, бессмысленно. Однако, если Вы раскроете контекст Вашей сложной математической задачи, то станет яснее, что Вы имеете в виду.

[маткиб]

akram_jadid писал(а):

Почти во всех источниках дается определения сложности в частных случаях. Напр.: сложность алгоритмов, сложность вычесления и т.д...
Я, в процесе построения ряда логических цепочек столкнулся с необходимостью определения понятия сложности. И естественно с необходимостью определения понятия "степень сложности". Что мы понимаем под словом "сложность" ? Этот вопрос я задал кондидату технических наук, и удовлитворительного ответа не получил....
Я пытаюсь решить очень сложную матеметическую задачу, которое пока что путем вычеслений решить не удается. Вы все слижком углубились в какой то области, и не видите дальше носа...
Правда, я сам попытался опредилить что такое сложность. Для этого мне пришлось ввести новое понятия, новый термин "количество знания". Если кто то откликнется, я готов обсудить свои идеии...

Ну определять, что такое сложность ВООБЩЕ, - это как-то слишком оптимистично, по-моему, как бы пустого словоблудия не получилось. Но если какие-то идеи у тебя уже есть, то выкладывай тут, будут обсуждать.

[akram_jadid]

SAN_666 писал(а):

Сложность - субъективное понятие, которым пользуются любители математики, и только они.

Ели это так, то из этого следует, что один из основателей теории сложности М. Джексон - любитель математики, который пользуется таким "субъективным" понятием, как "сложность".
Теорема: Задачи с высшей степенью сложности имеют простые решения.
Задача: Доказать или опровергнуть эту теорему.
Если мы в этом направлении придем к каким-нибудь результатам, то возможно, я пойду дальше и расскажу об этой "сложной математической" задаче.
Возможно, эта теорема неправильно сформулирована, или она не имеет места, не важно!
Мне нужны дополнительные идеи, пусть даже самые невероятные. Если кто-нибудь скажет, что я ничего не смыслю в математике, я не обижусь...
У меня очень мало времени, хотя я могу продолжать думать над этой проблемой годами. К формулировки этой теоремы я шел достаточно долго, но она всего лишь часть достаточно длинной логической цепочки рассуждений.
Мне просто хочется проверить свои идеи, отталкиваясь от ваших мнений, чтобы избежать роковой ошибки, с которой может столкнуться каждый из нас. Я не считаю, что я прав, я ищу правду!

[Anton Nonko]

akram_jadid в сообщении #141317 писал(а):

Теорема: Задачи с высшей степенью сложности имеют простые решения.
Задача: Доказать или опровергнуть эту теорему.

Это никакая не математическая задача до тех пор, пока вы не определили следующие понятия и отношения между ними: "задача", "степень сложности", "решение", "простое решение", "высшая степень сложности".

[Профессор Снэйп]

Я знаком с "теорией сложности" как с одним из разделов теории алгоритмов, изучающим различные вычислимые функции с точки зрения количества ресурсов (в основном таких, как время и объём памяти), которые машины тратят на их вычисление. В принципе, понятно, что оптимизация компьютерных программ по минимизации объёма памяти и быстродействию во многом зависит от искусства программистов, эти программы пишуших. Однако нельзя не признать, что зачастую в самих функциях заложена некоторая "внутренняя сложность", не позволяющая вычислять их посредством малого количества элементарных операций при большой длине входных данных.

К примеру, рассмотрим компьютер (с потенциально бесконечной памятью, в теоретических исследованиях обычно фигурирует машина Тьюринга), которому надо вычислять функции $f(x) = x$ и $g(x) = 2^x$. Аргументы функций --- натуральные числа (в десятичной или в двоичной записи), значения тоже, естественно, принадлежат $\mathbb{N}$. Для функции $f$ существует очень быстрая программа, которая просто копирует входные данные на устройство вывода, не производя никаких дополнительных преобразований. Время её работы на всех достаточно больших аргументах $x$ измеряется величиной порядка $O(\log(x))$ шагов. Между тем любая программа, вычисляющая функцию $g$, при достаточно больших $x$ будет работать значительно дольше, ибо длина результата вычислений уже имеет порядок $O(x)$ и, чтобы вывести этот результат (напечатать на принтере или занести на ленту машины Тьюринга), требуется время того же порядка. В этой ситуации говорят, что вычислительная сложность функции $g$ больше, чем вычислительная сложность функции $f$. И такая вот сложность является основным предметом рассмотрения теории, о которой спрашивает автор темы.

Должен признаться, что хоть я сам и занимаюсь теорией вычислимости, но всегда больше интересовался абстрактной её частью (иерархии, степени вычислимости различных типов, вычислимые модели). А с теорией сложности, имеющей более прикладной характер (хотя там есть довольно впечатляющие своей красотой чисто теоретические факты, вроде теоремы Блюм об ускорении) знаком весьма поверхностно. В частности, сказать точно, что понимается под "степенью сложности", я сейчас не возьмусь (да и, скорее всего, их там известно много разновидностей). Отмечу лишь, что в последние 30-40 лет теория сложности весьма популярна и востребована. Достаточно упомянуть тот факт, что одна из семи проблем тысячелетия, а именно, проблема "$\mathcal{P} = \mathcal{NP}$?", относится именно к ней.

Некоторые милые сердцу специалиста по абстрактной вычислимости факты, которые можно отнести к теории сложности, есть здесь, стр. 111 -- 130 (это то, что я сам читаю первокурсникам в НГУ). Не сомневаюсь, что в сети можно найти значительно более полные и подробные учебные материалы, относящиеся к сложности вычислений. Оставляю возможность дать соответствующие ссылки специалистам, лучше меня знакомым с обсуждаемым предметом. Таких специалистов здесь на форуме немало и они, без сомнения, сделают это лучше, чем я.

[Sonic86]

В курсе теории алгоритмов, предложенной Профессором Снейпом, на стр. 100 в примечании я нашел следующее:
"Есть классическая задача для программистов, которая заключается в том, чтобы написать программу, выводящую на экране свой собственный текст. ... теорема о неподвижной точке утверждает, что можно написать такую команду, которая не использует команд обращения к файлам, а лишь команду вывода на экран..."
Очень было бы интересно посмотреть на такую программу (желательно на С++ или на Pascal).
У нас на работе товарищи программисты очень удивились, что такая программа есть, хотя сомневались. Между тем, не могу представить себе код программы. Только вижу, что там должен быть цикл. И вопрос: в команде вывода параметры цикла можно использовать или нельзя (то есть происходит вывод только строк-констант?)?

[Профессор Снэйп]

Я слышал, что таких программ больше сотни известно. Поройтесь в интернете, там должны быть тексты. Причём очень короткие.

Цикл, думаю, не обязателен. А вот что там точно будет, так это строковые переменные, содержащие в качестве значений куски текста исходной программы.

P. S. После трёх минут поиска в гугле нашёл вот это: http://khpi-iip.mipk.kharkiv.edu/librar ... n/ken.html

[MaximKat]

ключевое слово для поиска - quine

[вздымщик Цыпа]

void main() { char *c="void main() { char *c=%c%s%c; printf(c,34,c,34); }"; printf(c,34,c,34); }

Самая короткая, какую я знаю. Ее придумал один мой приятель много лет назад, так что на инет сослаться не могу.

[Echo-Off]

VAR S:STRING;BEGIN S:='VAR S:STRING;BEGIN S:=;Write(Copy(S,1,22),#39,s,#39,Copy(S,23,49))END.';Write(Copy(S,1,22),#39,s,#39,Copy(S,23,49))END.

Добавлено спустя 2 минуты 2 секунды:

Впрочем, на некоторых языках самовыводящаяся программа занимает всего 1 символ