dmitgu (dmitgu) wrote,
dmitgu
dmitgu

... 6, пп. 2.1-2.3. Задачи … из класса NP

к Оглавлению

2.1. «Персональную подсказку» для алгоритма-решения «Эдип» алгоритм «Сфинкс» будет выдавать при следующих аргументах, (пояснения в следующих двух подпунктах):

Sph(«Oed(«Sph(…, …, …)», «-», …)», t, y) = 0

Где алгоритм долга у «Эдипа» равен «объективно» (символ прочерка), у «Сфинкса» он равен «Эдипу» с аргументом долга «объективно», теорема t фиксирована, а результат 0 получается при любом доказательстве y за время, полиномиальное относительно размеров |t| иOedSph(…, …, …)», «-», t)»|.

И тогда корректный «Эдип» должен понять «персональную подсказку» для себя от «Сфинкса» и вернуть 0 (Ноль):

OedSph(…, …, …)», «-», t) = 0

2.2. Пояснение к пункту 2.1 о разных местах подстановки аргументов:

Аргумент-теорема t в OedSph(…, …, …)», «-», …) не указывается, раз он указан в «Сфинксе»:

Sph(«Oed(«Sph(…, …, …)», «-», …)», t, y). Не может же «Эдип» искать одно, а «Сфинкс» проверять другое. А вот аргумент долга «Эдипа» должен быть задан подстановкой в алгоритме «Эдип» - который содержится в аргументе долга «Сфинкса». Дело вот в чём:

У «Сфинкса» аргумент долга имеет большую вложенность, чем соответствующий ему аргумент долга у «Эдипа» (или другого алгоритма-решения), если мы говорим про аргумент долга «Сфинкса», которые отличается от «объективно».

И мы не будем разбивать аргумент долга на составляющие – «кто рассказывает» («Эдип»), «с точки зрения кого рассказывает» («Объективно» - в разбираемом случае), потому что тогда нам и того «с точки зрения кого» придётся разбивать на «кто» и «с точки зрения кого» и т.д. Вложенность может быть любой и нам не хватит тогда никаких аргументов.

2.3. Пояснение к пункту 2.1 о способе подстановки аргументов в один алгоритм с получением другого алгоритма:

Алгоритм по превращению одного текста алгоритма в другой – с подставленным первым аргументом – можно изображать так: Arg1(«MyArg», «A(… , …)»). Мы использовали выше и продолжим использовать далее обозначения типа BA(…, …)», x), BA(…, …)», …) и т.п. Подразумевается, что таким образом мы используем какой-то стандартный известный способ по превращению алгоритма, зависящего от нескольких аргументов в некие другие алгоритмы – в которых часть аргументов (или даже все) исходного алгоритма уже подставлена. А можем передавать тексты алгоритмов и без подставленных аргументов, как, например «A(…, …)».

Тут есть важное различие между двумя способами использования 1-го (без потери общности пусть будет 1-й) аргумента в алгоритме A_1(x1, x2, …):

2.3.1. Фиксацией некоторого значения «text в аргументе x1 алгоритма A_1(x1, x2, …) и превращения его в новый алгоритм A_2(x2, x3, …);

2.3.2. Использование алгоритма A_1(x1, x2, …) и его аргументов обычным образом: сначала заполняется (вне рамок инструкций и работы алгоритма A_1(x1, x2, …)) информация о значениях аргументов там, где алгоритм A_1(x1, x2, …) ожидает найти эту информацию, а затем запускается алгоритм A_1(x1, x2, …).

Важное отличие между 2.3.1 и 2.3.2 в том, что в случае 2.3.1 время на присваивание переменной x1 значения «text является частью времени работы алгоритма A_2(x2, x3, …), а размер этой операции – включая размер текста «text - является частью размера алгоритма A_2(x2, x3, …). Поэтому в случае 2.3.1 мы не можем рассматривать значение переменной x1 как полученное по ссылке (когда передаётся адрес места, где находятся данные, а не сами данные – байт за байтом).

При использовании алгоритмов в духе варианта 2.3.1 будем использовать обозначение A_1(«text1», x2, …), что по виду не отличается от варианта 2.3.2 при аргументе x1 со значением «text. Но если по контексту будет не ясно, какой из вариантов имеется в виду, то будем это специально оговаривать.

Например, на место первого аргумента внутри формулы:

Sph(«Oed(«Sph(…, …, …)», «-», …)», t, y)

подставлен программный текст «OedSph(…, …, …)», «-», …)». И в этом программном тексте подстановка в первый и второй аргументы значений «Sph(…, …, …)» и «-» выполнены по варианту 2.3.1. И всегда для аргумента, который относится к подстановке внутри текста программы или текста логической формулы мы будем использовать вариант 2.3.1.

А если аргумент не является частью текста программы/логической формулы – может быть и вариант 2.3.1 и вариант 2.3.2. Например, в разбираемом сейчас алгоритме

SphOedSph(…, …, …)», «-», …)», t, y)

аргумент y – подставляется по варианту 2.3.2. Ведь время работы данного алгоритма не зависит от размера слишком больших аргументов y и поэтому аргумент y – именно аргумент, размер которого и время, расходуемое на заполнение аргумента значением, не являются ни частью размера разбираемого алгоритма, ни частью времени его работы.

Более того, аргумент y передаётся по ссылке, чтобы не передавать байт за байтом ненужную (при слишком большом размере значения аргумента y) информацию при использовании «Сфинкса».

Разницу между вариантом 2.3.1 и 2.3.2 можно практически наблюдать на примере программы из подраздела  5.2 «Теорема о построении алгоритма, применяемого к себе». Там видно, что изначально нет операции присваивания «аргументу» x (хотя там аргумент представлен «готовой» переменной). Программа просто использует готовое значение из x и только с этого момента отсчитывается её размер и время её работы. А в процессе исполнения процедуры диагонализации присваивание становится частью «тела» и процесса работы итоговой программы.

И в подразделе 5.1 «Лемма о диагонализации» формула B(diag(«B(diag(x))»)), используемая в доказательстве Леммы, понимается в смысле варианта 2.3.1.


Tags: NP≠P дискуссии, ЖЖвЖЖ математика
Subscribe

  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 0 comments